Frog Jump

Hard

#0390Time: O(N^2). We iterate through `N` stones. For each stone `i`, the number of jumps in its set is at most `i`. The total number of jump calculations is the sum of `i` from 0 to `N-1`, which is `O(N^2)`. Map operations are on average O(1).Space: O(N^2). The map stores `N` keys. The total number of elements across all sets can be up to `O(N^2)` in the worst case, as the number of possible jump sizes to reach stone `i` can be `O(i)`.5 companies

Patterns

Dynamic Programming

Data structures

Array

Companies

Snap PhonePe Zomato LINE

Prompt

A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones positions (in units) in sorted ascending order, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit.

If the frog's last jump was k units, its next jump must be either k - 1, k, or k + 1 units. The frog can only jump in the forward direction.

Example 1:

Input: stones = [0,1,3,5,6,8,12,17]
Output: true
Explanation: The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.

Example 2:

Input: stones = [0,1,2,3,4,8,9,11]
Output: false
Explanation: There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.

Constraints:

2 <= stones.length <= 2000
0 <= stones[i] <= 2³¹ - 1
stones[0] == 0
stones is sorted in a strictly increasing order.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a bottom-up dynamic programming strategy, which is often implemented iteratively. It can be thought of as a Breadth-First Search (BFS) on the state space. We build up the solution by finding all possible jump sizes that can reach each stone, starting from the first stone.

Algorithm

Create a HashMap<Integer, Set<Integer>> to store, for each stone position, the set of jump sizes that can be made from it.
Initialize the map with all stone positions and empty sets.
Add a jump of size 1 to the set for the first stone (at position 0): map.get(0).add(1).
Iterate through the stones array from i = 0 to n-1.
For the current stone stones[i], get its set of possible jumps from the map.
For each jump k in the set:
- Calculate nextPos = stones[i] + k.
- If nextPos is the position of the last stone, return true.
- If there is a stone at nextPos (check using the map), update the set for nextPos by adding k-1 (if > 0), k, and k+1.
If the loops complete without reaching the last stone, return false.

Walkthrough

We use a HashMap where the keys are the stone positions and the values are Sets of integers. map.get(stone_pos) will store the set of jump sizes that can be made from the stone at stone_pos.

First, we initialize the map for all stone positions with empty sets. The frog starts at stones[0] (position 0) and must make a jump of size 1. So, we initialize map.get(0).add(1). We then iterate through the stones in their given order. For each stone, we look at the set of possible jump sizes k from it. For each jump size k, we calculate the next_position = stone + k. If a stone exists at next_position, we update its entry in the map. Since the last jump was k, the next jump from next_position can be k-1, k, or k+1. We add these valid (positive) jump sizes to the set for next_position.

After iterating through all stones up to the second to last, if we have managed to schedule a jump to the last stone, we return true. If the entire process completes and the last stone was never reached, it's impossible.

1import java.util.HashMap;2import java.util.HashSet;3import java.util.Map;4import java.util.Set;5 6public class Solution {7    public boolean canCross(int[] stones) {8        Map<Integer, Set<Integer>> map = new HashMap<>();9        for (int stone : stones) {10            map.put(stone, new HashSet<>());11        }12        13        // First jump is 1 unit from stone 0.14        // This requires a stone at position 1.15        if (!map.containsKey(1) || stones[1] != 1) {16            return false;17        }18 19        map.get(0).add(1);20 21        for (int i = 0; i < stones.length; i++) {22            int currentStone = stones[i];23            Set<Integer> jumps = map.get(currentStone);24            for (int k : jumps) {25                int nextPos = currentStone + k;26                if (nextPos == stones[stones.length - 1]) {27                    return true;28                }29                if (map.containsKey(nextPos)) {30                    Set<Integer> nextJumps = map.get(nextPos);31                    if (k - 1 > 0) {32                        nextJumps.add(k - 1);33                    }34                    nextJumps.add(k);35                    nextJumps.add(k + 1);36                }37            }38        }39 40        return false;41    }42}

Complexity

Time

O(N^2). We iterate through `N` stones. For each stone `i`, the number of jumps in its set is at most `i`. The total number of jump calculations is the sum of `i` from 0 to `N-1`, which is `O(N^2)`. Map operations are on average O(1).

Space

O(N^2). The map stores `N` keys. The total number of elements across all sets can be up to `O(N^2)` in the worst case, as the number of possible jump sizes to reach stone `i` can be `O(i)`.

Trade-offs

Pros

Generally more efficient in practice than recursion due to avoiding call stack overhead.
It's a systematic, level-by-level (stone-by-stone) exploration of reachable states.

Cons

Can use significant memory, O(N^2), similar to the memoization approach.

This approach uses a simple recursive function to explore all possible jump sequences from the starting stone. The state of the frog is defined by its current stone index and the size of the last jump. From each stone, it tries to jump to the next possible stones with jump sizes k-1, k, or k+1.

Algorithm

Define a recursive function canCrossRecursive(stones, index, k).
Base Case: If index is the last stone (stones.length - 1), return true.
Iterate from i = index + 1 to the end of the stones array.
Calculate the gap: gap = stones[i] - stones[index].
If gap is a valid next jump (i.e., k-1 <= gap <= k+1), make a recursive call canCrossRecursive(stones, i, gap).
If the recursive call returns true, return true immediately.
An optimization: if gap > k + 1, we can break the inner loop since subsequent gaps will be even larger.
If the loop finishes without finding a path, return false.
The initial call is canCrossRecursive(stones, 1, 1) after checking that stones[1] == 1.

Walkthrough

We define a recursive function canCross(index, k) which returns true if the frog can reach the last stone from stones[index], given the last jump was of size k.

The base case for success is when index is the last stone's index (n-1).

In the recursive step, we iterate through the three possible next jump sizes: k-1, k, and k+1. We only consider positive jump sizes. For each valid next jump size nextK, we calculate the target position targetPos = stones[index] + nextK. We then search for a stone at targetPos in the rest of the array (from index + 1 onwards). If we find such a stone at nextIndex, we make a recursive call canCross(nextIndex, nextK). If this call returns true, it means a path exists, and we propagate true up the call stack.

If all possible jumps from the current stone lead to dead ends, the function returns false.

The initial call is made after checking the first jump. The first jump from stones[0] (position 0) must be 1 unit. This requires a stone to be at position 1. If stones[1] is not 1, it's impossible. Otherwise, the first recursive call is canCross(1, 1).

1public class Solution {2    public boolean canCross(int[] stones) {3        // The first jump must be 1 unit, so a stone must exist at position 1.4        if (stones[1] != 1) {5            return false;6        }7        return canCrossRecursive(stones, 1, 1);8    }9 10    private boolean canCrossRecursive(int[] stones, int index, int k) {11        // If we have reached the last stone, we have succeeded.12        if (index == stones.length - 1) {13            return true;14        }15 16        // Explore subsequent stones as potential next steps.17        for (int i = index + 1; i < stones.length; i++) {18            int gap = stones[i] - stones[index];19            // Check if the jump to the next stone is valid.20            if (gap >= k - 1 && gap <= k + 1) {21                if (canCrossRecursive(stones, i, gap)) {22                    return true;23                }24            }25            // Optimization: Since the stones array is sorted, if the current gap26            // is already larger than k+1, subsequent gaps will be even larger.27            // So, we can stop searching from this point.28            if (gap > k + 1) {29                break;30            }31        }32 33        return false;34    }35}

Complexity

Time

O(3^N). At each stone, we can potentially branch out to 3 other stones. In the worst case, the recursion tree can have a depth of N, leading to an exponential number of calls.

Space

O(N), where N is the number of stones. This is due to the maximum depth of the recursion stack.

Trade-offs

Pros

Simple to understand and implement.
Follows the problem's logic directly.

Cons

Extremely inefficient due to re-computing results for the same states (index, k) multiple times.
Will likely result in a 'Time Limit Exceeded' error for larger inputs.

This approach improves upon the brute-force recursion by using memoization to store the results of subproblems. This avoids redundant computations for the same state, which is defined by (current_index, last_jump_size). A 2D array or a hash map can be used as a cache.

Algorithm

Pre-process stones into a HashMap for O(1) position-to-index lookups.
Create a memoization table, e.g., a 2D array memo[N][N], initialized to a value indicating 'not computed'.
Define a recursive function canCrossMemo(index, k, ...) that takes the memo table as an argument.
Inside the function, first check if memo[index][k] has been computed. If so, return the stored value.
If not, perform the same logic as the brute-force approach to find the result.
For each possible next jump nextK in {k-1, k, k+1}:
- Calculate nextPos = stones[index] + nextK.
- If a stone exists at nextPos, find its index nextIndex using the map.
- Make a recursive call canCrossMemo(nextIndex, nextK, ...).
- If the call returns true, store true in the memo table and return.
If all jumps fail, store false in the memo table and return.
The initial call is canCrossMemo(1, 1, ...) after checking stones[1] == 1.

Walkthrough

We use a 2D array, memo, where memo[index][k] stores the result of whether the frog can cross from stones[index] with a last jump of size k. Before computing the result for a state (index, k), we first check our memo table. If the result is already there, we return it directly. If not, we compute it using the same recursive logic as the brute-force approach. Once the result is computed, we store it in memo[index][k] before returning.

To quickly find the index of the next stone given its position, we can pre-process the stones array into a HashMap that maps stone positions to their indices. This reduces the search for the next stone from O(N) to O(1). The state space for k (last jump size) can be up to N, as the i-th jump can be at most i+1. So the memoization table size will be N x N.

1import java.util.HashMap;2import java.util.Map;3 4public class Solution {5    public boolean canCross(int[] stones) {6        if (stones[1] != 1) {7            return false;8        }9        Map<Integer, Integer> stonePositions = new HashMap<>();10        for (int i = 0; i < stones.length; i++) {11            stonePositions.put(stones[i], i);12        }13        // Using a 2D array for memoization. -1: not computed, 0: false, 1: true14        int[][] memo = new int[stones.length][stones.length + 1];15        for (int i = 0; i < memo.length; i++) {16            java.util.Arrays.fill(memo[i], -1);17        }18        return canCrossMemo(stones, 1, 1, stonePositions, memo);19    }20 21    private boolean canCrossMemo(int[] stones, int index, int k, Map<Integer, Integer> stonePositions, int[][] memo) {22        if (index == stones.length - 1) {23            return true;24        }25        if (memo[index][k] != -1) {26            return memo[index][k] == 1;27        }28 29        for (int nextK = k - 1; nextK <= k + 1; nextK++) {30            if (nextK > 0) {31                int nextPos = stones[index] + nextK;32                if (stonePositions.containsKey(nextPos)) {33                    int nextIndex = stonePositions.get(nextPos);34                    if (canCrossMemo(stones, nextIndex, nextK, stonePositions, memo)) {35                        memo[index][k] = 1;36                        return true;37                    }38                }39            }40        }41 42        memo[index][k] = 0;43        return false;44    }45}

Complexity

Time

O(N^2). Each state `(index, k)` is computed only once. There are `N` possible indices and at most `N` possible jump sizes `k`. The work inside each function call is constant time on average (due to HashMap lookups).

Space

O(N^2). The memoization table requires `O(N^2)` space. The recursion stack depth is `O(N)`, and the stone position map is `O(N)`. The dominant factor is the memoization table.

Trade-offs

Pros

Significantly faster than brute-force by eliminating redundant computations.
Guaranteed to run in polynomial time, making it feasible for the given constraints.

Cons

Requires significant memory, O(N^2), for the memoization table, which can be large for N=2000.

Solutions

Solution

1class Solution { private Boolean [][] f ; private Map < Integer , Integer > pos = new HashMap <>(); private int [] stones ; private int n ; public boolean canCross ( int [] stones ) { n = stones . length ; f = new Boolean [ n ][ n ]; this . stones = stones ; for ( int i = 0 ; i < n ; ++ i ) { pos . put ( stones [ i ], i ); } return dfs ( 0 , 0 ); } private boolean dfs ( int i , int k ) { if ( i == n - 1 ) { return true ; } if ( f [ i ][ k ] != null ) { return f [ i ][ k ]; } for ( int j = k - 1 ; j <= k + 1 ; ++ j ) { if ( j > 0 ) { int h = stones [ i ] + j ; if ( pos . containsKey ( h ) && dfs ( pos . get ( h ), j )) { return f [ i ][ k ] = true ; } } } return f [ i ][ k ] = false ; } }

1class Solution : def canCross ( self , stones : List [ int ]) -> bool : @ cache def dfs ( i , k ): if i == n - 1 : return True for j in range ( k - 1 , k + 2 ): if j > 0 and stones [ i ] + j in pos and dfs ( pos [ stones [ i ] + j ], j ): return True return False n = len ( stones ) pos = { s : i for i , s in enumerate ( stones )} return dfs ( 0 , 0 )

1class Solution { public: bool canCross ( vector < int >& stones ) { int n = stones . size (); int f [ n ][ n ]; memset ( f , - 1 , sizeof ( f )); unordered_map < int , int > pos ; for ( int i = 0 ; i < n ; ++ i ) { pos [ stones [ i ]] = i ; } function < bool ( int , int ) > dfs = [ & ]( int i , int k ) -> bool { if ( i == n - 1 ) { return true ; } if ( f [ i ][ k ] != - 1 ) { return f [ i ][ k ]; } for ( int j = k - 1 ; j <= k + 1 ; ++ j ) { if ( j > 0 && pos . count ( stones [ i ] + j ) && dfs ( pos [ stones [ i ] + j ], j )) { return f [ i ][ k ] = true ; } } return f [ i ][ k ] = false ; }; return dfs ( 0 , 0 ); } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution { private Boolean [][] f ; private Map < Integer , Integer > pos = new HashMap <>(); private int [] stones ; private int n ; public boolean canCross ( int [] stones ) { n = stones . length ; f = new Boolean [ n ][ n ]; this . stones = stones ; for ( int i = 0 ; i < n ; ++ i ) { pos . put ( stones [ i ], i ); } return dfs ( 0 , 0 ); } private boolean dfs ( int i , int k ) { if ( i == n - 1 ) { return true ; } if ( f [ i ][ k ] != null ) { return f [ i ][ k ]; } for ( int j = k - 1 ; j <= k + 1 ; ++ j ) { if ( j > 0 ) { int h = stones [ i ] + j ; if ( pos . containsKey ( h ) && dfs ( pos . get ( h ), j )) { return f [ i ][ k ] = true ; } } } return f [ i ][ k ] = false ; } }

1class Solution : def canCross ( self , stones : List [ int ]) -> bool : @ cache def dfs ( i , k ): if i == n - 1 : return True for j in range ( k - 1 , k + 2 ): if j > 0 and stones [ i ] + j in pos and dfs ( pos [ stones [ i ] + j ], j ): return True return False n = len ( stones ) pos = { s : i for i , s in enumerate ( stones )} return dfs ( 0 , 0 )

1class Solution { public: bool canCross ( vector < int >& stones ) { int n = stones . size (); int f [ n ][ n ]; memset ( f , - 1 , sizeof ( f )); unordered_map < int , int > pos ; for ( int i = 0 ; i < n ; ++ i ) { pos [ stones [ i ]] = i ; } function < bool ( int , int ) > dfs = [ & ]( int i , int k ) -> bool { if ( i == n - 1 ) { return true ; } if ( f [ i ][ k ] != - 1 ) { return f [ i ][ k ]; } for ( int j = k - 1 ; j <= k + 1 ; ++ j ) { if ( j > 0 && pos . count ( stones [ i ] + j ) && dfs ( pos [ stones [ i ] + j ], j )) { return f [ i ][ k ] = true ; } } return f [ i ][ k ] = false ; }; return dfs ( 0 , 0 ); } };

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.