[GO] [100%] FrogRiverOne (src & jUnit)

Painless

FrogRiverOne

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

Task description

A little frog wants to go across the river. The frog is initially on one bank of the river (position 0) and wants to go to the other bank (position X + 1). Leaves fall from the tree to the surface of the river.

Given an array A consisting of N integers representing fallen leaves. A [K] indicates the position where one leaf falls at time K in seconds.

The goal is to find the earliest time the frog can jump to the other side of the river. Frogs can only cross if leaves appear in all positions 1 through X of the river (that is, they want to find the earliest moment when all positions 1 through X are covered with leaves). The velocity of the river flow can be considered to be negligible. In other words, when the leaves fall into the river, the position of the leaves does not change.

For example, given the integer X = 5 and the array A:

  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 the second 6, the leaves fall to position 5. This is the earliest time for leaves to appear at all locations across the river.

Write a function:

class solution {public int solution（int X、int [] A）; }

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

If the frog cannot jump to the other side of the river, the function should return -1.

For example, suppose X = 5 and array A looks like this:

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

As explained above, the function should return 6.

Write an efficient algorithm for the following assumptions:

N and X are integers in the range [1..100,000].
Each element of array A is an integer in the range [1..X].

solve

Program FrogRiverOneSolution.java

`FrogRiverOneSolution.java`


    public int solution(int X, int[] A) {
        int goal = -1;
        int B[] = new int[X + 1];
        java.util.Arrays.fill(B, -1);
        for (int i = 0; i < A.length; i++) {
            if (B[A[i]] < 0 || B[A[i]] > i) {
                B[A[i]] = i;
            }
        }

        for (int j = 1; j < B.length; j ++) {
            int anB = B[j];
            if (anB < 0) {
                goal = -1;
                break;
            } else {
                goal = goal < anB ? anB : goal;
            }
        }

        return goal;
    }

Detected time complexity:
O(N)

jUnit FrogRiverOneSolutionTest.java

Report Candidate Report: training933GQH-AM9