[Codility - Java] 4. Counting Elements - 1. FrogRiverOne

FrogRiverOne

Find the earliest time when a frog can jump to the other side of a river.

A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river.

You are given an array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds.

The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X (that is, we want to find the earliest moment when all the positions from 1 to X are covered by leaves). You may assume that the speed of the current in the river is negligibly small, i.e. the leaves do not change their positions once they fall in the river.

For example, you are given integer X = 5 and array A such that:

A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4

In second 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.

Write a function:

class Solution { public int solution(int X, int[] A); }

that, given a non-empty array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.

If the frog is never able to jump to the other side of the river, the function should return −1.

For example, given X = 5 and array A such that:

A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4

the function should return 6, as explained above.

Write an efficient algorithm for the following assumptions:

• N and X are integers within the range [1..100,000];
• each element of array A is an integer within the range [1..X].

---

개구리는 0 위치에 있고, X + 1로 가고 싶어한다.

강 표면에는 나뭇잎이 떠있습니다.

N개의 정수로 구성된 배열 A (배열 A는 비어있지 않습니다.)
A[K] 에는 K 초에 측정된 나뭇잎 위치가 들어있습니다.

A[0]은 0초에 떨어진 나뭇잎, A[1]은 1초에 떨어진 나뭇잎

개구리는 위치 1부터 위치 X까지 모든 낙엽이 띄워져 있어야 반대편으로 갈 수 있습니다.

개구리가 몇 초가 지나야 강 반대편으로 넘어갈 수 있는지 구하면 됩니다.
만일, 넘어갈 수 없다면 -1을 리턴하세요.

1 <= N, X <= 100,000

배열 A를 순회하면서 set에 요소를 넣고,
set 크기가 X 가 같아지면 반복문을 종료하면 됩니다.
반복문을 모두 돈 후에도 X와 set 크기가 같은 경우가 없다면 -1을 리턴하면 됩니다.

static int frogRiverOne(int[] A, int X) {
    int result = -1;
    Set<Integer> s = new HashSet<>();
    for (int i = 0; i < A.length; i++) {
        s.add(A[i]);
        if (X == s.size()) {
            result = i;
            break;
        }
    }
    return result;
}

$O(N)$