Implementing Frog River One in Java

1. Introduction

In this tutorial, we’ll learn about the Frog River One problem.

2. Problem Statement

In this problem, a frog wants to cross a river. It can do so only if there’s a leaf path connecting the two sides. As leaves fall from a nearby tree, the path will eventually form, and the frog will be able to cross. The question is when.

Formally, the river is like a sequence of m positions: the starting position is 1, and the destination corresponds to m. A non-empty array leaves contains n integers (from 1 to m) such that leaves[k] represents the position where a leaf falls at time step k. We assume that n >= m and count time steps from 0. We return time steps counting from 0.

Our objective is to find the minimum number of time steps at which the frog can arrive at its destination. If it can never cross the river, we return -1.

2.1. Example

Let m = 5 and leaves = [1, 3, 1, 4, 5, 4, 2, 3].

Initially, k = 0, and a leaf falls at position 1 since leaves[0] = 1. We needs the leaves at positions 2-5 as well to cross. The path forms over time as the leaves fall:

So, the frog can cross the river at time step k = 6. As we count from 0, we return 7 (6+1).

3. Set-Based Approach

The naive approach is to check whether the path is complete at every time step. This involves an outer loop and an inner nested loop. It has a quadratic time complexity, O(n²).

A better approach is to keep track of the unique positions that have been already covered. For this, we use a HashSet to store the distinct positions covered so far:

1. Iterate through the array leaves with index k (representing time step).
   1. We add leaves[k] it to our hashset.
   2. Check the size of the set.
   3. If the size equals m, it means we have collected leaves at all positions from 1 to m. So, we return k+1 immediately, as this is the earliest time of possible crossing.
   4. Otherwise, we continue the loop.
2. If the loop finishes without the set size reaching m, then no solution is possible, and we return -1.

3.1. Implementation

Here is the implementation:

public int HashSetSolution(int m, @Nonnull int[] leaves) {
    Set leavesCovered = new HashSet<>();
    int status = -1;
    for (int k = 0; k < leaves.length; k++) {
        int position = leaves[k];
        leavesCovered.add(position);      
        if (leavesCovered.size() == m) {
            status = k+1;
            return status;
        }
    }
}

We use a HashSet (leavesCovered) to store the covered leaves. We iterate over input leaves and add each position to leavesCovered (HashSet doesn’t keep duplicates). Then, we check if the size of leavesCovered is equal to m. If so, we return k+1 as our solution (since time steps start from 0, we need to add 1). If we loop out, then there is no solution, so we return -1.

3.2. Testing

Let’s dry-run this solution with a couple of unit test cases.

In the test case whenLeavesCoverPath_thenReturnsEarliestTime(), we set m=7 and leaves=[1, 3, 6, 4, 2, 3, 7, 5, 4]. Here, the leaves are filled with all positions from 1 to 7. We iterate over leaves and stop at time step k = 7. Hence, the frog takes 8 time steps, as asserted:

@Test
void whenLeavesCoverPath_thenReturnsEarliestTime() {
    int m = 7;
    int[] leaves = {1, 3, 6, 4, 2, 3, 7, 5, 4};
    assertEquals(8, frogRiverOne.HashSetSolution(m, leaves));
}

In whenLeavesAreMissing_thenReturnsMinusOne(), no leaf falls onto position 5, so there is no path between the two sides. As a result, we get -1:

@Test
void whenLeavesAreMissing_thenReturnsMinusOne() {
    int m = 7;
    int[] leaves = {1, 3, 6, 4, 2, 3, 7, 4};  // 5 is missing
    assertEquals(-1, frogRiverOne.HashSetSolution(m, leaves));
}

3.3. Time and Space Complexity

A HashSet-based solution’s average time complexity is O(n) since we iterate through the array exactly once, and HashSet operations add() and size() are O(1) on average.

However, HashSet suffers from a collision problem: if many elements hash to the same bucket, it converts to a balanced tree in Java. In the worst-case scenario of continuous hash collisions, add() has a logarithmic complexity: O(log n). Therefore, this approach has the loglinear O(n log n) time complexity.

The space complexity is O(n + m). Since m <= n, it reduces to O(n).

4. Bitmap-Based Solution

Here, we use a boolean array of size m + 1 as a bitmap to map positions 1 to m directly to leaf indices. We use it to track the covered positions. The boolean array provides a strict O(1) lookup time for each element.

Here is our approach:

1. We initialize the bitmap to monitor all positions across the river that have received a leaf, starting with all positions marked as empty.
2. Then, we initialize a counter to track the number of uncovered positions.
3. We iterate through leaves :
   1. We check the current leaf’s position to see if it has been covered.
   2. If not, we update the bitmap and decrement our counter by one.
   3. If the counter gets equal to zero, there is a path, and we return the time. Otherwise, we move to the next leaf.
4. If we loop out and the counter is > 0, leaves don’t form a complete path, so we return -1.

4.1. Implementation

Next, we move to the implementation:

public int BooleanArraySolution(int m, int[] leaves) {
    boolean[] leavesCovered = new boolean[m + 1];
    int leavesUncovered = m;
    for (int k = 0; k < leaves.length; k++) {
        int position = leaves[k];
        if (!leavesCovered[position]) {
            leavesCovered[position] = true;
            leavesUncovered--;
            if (leavesUncovered == 0) {
                return k+1;
            }
        }
    }
    return -1;
}

We use a boolean array (leavesCovered) with m + 1 elements to keep track of the leaves that fall. This way, we can map each leave position to our boolean array. leavesCovered.

We iterate over input leaves. For each leaf with index k, we check whether it has not already been visited. If yes, then we set this index to true in leavesCovered and decrement our tracker leavesUncovered by 1. Further, we return k+1 if our tracker leavesUncovered ==0. If we loop out, then there is no solution, so we return -1.

We use the same unit test cases as in the HashSet-based solution.

4.2. Time and Space Complexity

The average and worst-case time complexities of this solution are O(n), since it doesn’t suffer from collisions like the HashSet solution.

It also has the space complexity of O(n).

5. Conclusion

In this article, we solved the Frog River One problem using two approaches: a HashSet and a boolean array. The solution using a Boolean array guarantees a strict O(n) time complexity by avoiding hash collisions.

As always, the complete source code is available over on GitHub.