Partner – Moderne – NPI EA (cat=Spring Boot)
announcement - icon

Refactor Java code safely — and automatically — with OpenRewrite.

Refactoring big codebases by hand is slow, risky, and easy to put off. That’s where OpenRewrite comes in. The open-source framework for large-scale, automated code transformations helps teams modernize safely and consistently.

Each month, the creators and maintainers of OpenRewrite at Moderne run live, hands-on training sessions — one for newcomers and one for experienced users. You’ll see how recipes work, how to apply them across projects, and how to modernize code with confidence.

Join the next session, bring your questions, and learn how to automate the kind of work that usually eats your sprint time.

Course – Black Friday 2026 – NPI EA – main – before_post_content
announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW

Course – Black Friday 2026 – NPI – main – before_post_content
announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW

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:

Time Step (k) Leaf Position (leaves[k]) Covered Yet to Cover
0 1 1 2, 3, 4, 5
1 3 1, 3 2, 4, 5
2 1 1, 3 2, 4, 5
3 4 1, 3, 4 2, 5
4 5 1, 3, 4, 5 2
5 4 1, 3, 4, 5 5
6 2 1, 2, 3, 4, 5

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(n2).

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.

The code backing this article is available on GitHub. Once you're logged in as a Baeldung Pro Member, start learning and coding on the project.
Partner – Moderne – NPI EA (tag=Refactoring)
announcement - icon

Modern Java teams move fast — but codebases don’t always keep up. Frameworks change, dependencies drift, and tech debt builds until it starts to drag on delivery. OpenRewrite was built to fix that: an open-source refactoring engine that automates repetitive code changes while keeping developer intent intact.

The monthly training series, led by the creators and maintainers of OpenRewrite at Moderne, walks through real-world migrations and modernization patterns. Whether you’re new to recipes or ready to write your own, you’ll learn practical ways to refactor safely and at scale.

If you’ve ever wished refactoring felt as natural — and as fast — as writing code, this is a good place to start.

Course – Black Friday 2026 – NPI EA – main – after_post_content

announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW

Course – Black Friday 2026 – NPI – main – after_post_content

announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW