1. IntroductionIn this tutorial, we’ll learn about the Frog River One problem.2. Problem StatementIn 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. ExampleLet 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])CoveredYet to Cover0112, 3, 4, 5131, 32, 4, 5211, 32, 4, 5341, 3, 42, 5451, 3, 4, 52541, 3, 4, 55621, 2, 3, 4, 5So, the frog can cross the river at time step k = 6. As we count from 0, we return 7 (6+1).3. Set-Based ApproachThe 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:Iterate through the array leaves with index k (representing time step).We add leaves[k] it to our hashset.Check the size of the set.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.Otherwise, we continue the loop.If the loop finishes without the set size reaching m, then no solution is possible, and we return -1.3.1. ImplementationHere 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. TestingLet’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:@Testvoid 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:@Testvoid 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 ComplexityA 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 0, leaves don’t form a complete path, so we return -1.4.1. ImplementationNext, 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 ComplexityThe 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. ConclusionIn 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.The post Implementing Frog River One in Java first appeared on Baeldung.