# Frog Jump
**Difficulty:** HARD
[External](https://leetcode.com/problems/frog-jump)
Canonical: https://scaleengineer.com/dsa/problems/frog-jump
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Snap](https://scaleengineer.com/companies/snap), [PhonePe](https://scaleengineer.com/companies/phonepe), [Zomato](https://scaleengineer.com/companies/zomato), [LINE](https://scaleengineer.com/companies/line), [Otter.ai](https://scaleengineer.com/companies/otter.ai)
---
## Problem
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] <= 231 - 1`
* `stones[0] == 0`
* `stones` is sorted in a strictly increasing order.

# Approaches
## Brute-Force Recursion
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`.
**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.
**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.
### Explanation
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)`.

```java
public class Solution {
    public boolean canCross(int[] stones) {
        // The first jump must be 1 unit, so a stone must exist at position 1.
        if (stones[1] != 1) {
            return false;
        }
        return canCrossRecursive(stones, 1, 1);
    }

    private boolean canCrossRecursive(int[] stones, int index, int k) {
        // If we have reached the last stone, we have succeeded.
        if (index == stones.length - 1) {
            return true;
        }

        // Explore subsequent stones as potential next steps.
        for (int i = index + 1; i < stones.length; i++) {
            int gap = stones[i] - stones[index];
            // Check if the jump to the next stone is valid.
            if (gap >= k - 1 && gap <= k + 1) {
                if (canCrossRecursive(stones, i, gap)) {
                    return true;
                }
            }
            // Optimization: Since the stones array is sorted, if the current gap
            // is already larger than k+1, subsequent gaps will be even larger.
            // So, we can stop searching from this point.
            if (gap > k + 1) {
                break;
            }
        }

        return false;
    }
}
```
### 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`.

## Recursion with Memoization (Top-Down DP)
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.
**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.
**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.
### Explanation
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`.

```java
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public boolean canCross(int[] stones) {
        if (stones[1] != 1) {
            return false;
        }
        Map<Integer, Integer> stonePositions = new HashMap<>();
        for (int i = 0; i < stones.length; i++) {
            stonePositions.put(stones[i], i);
        }
        // Using a 2D array for memoization. -1: not computed, 0: false, 1: true
        int[][] memo = new int[stones.length][stones.length + 1];
        for (int i = 0; i < memo.length; i++) {
            java.util.Arrays.fill(memo[i], -1);
        }
        return canCrossMemo(stones, 1, 1, stonePositions, memo);
    }

    private boolean canCrossMemo(int[] stones, int index, int k, Map<Integer, Integer> stonePositions, int[][] memo) {
        if (index == stones.length - 1) {
            return true;
        }
        if (memo[index][k] != -1) {
            return memo[index][k] == 1;
        }

        for (int nextK = k - 1; nextK <= k + 1; nextK++) {
            if (nextK > 0) {
                int nextPos = stones[index] + nextK;
                if (stonePositions.containsKey(nextPos)) {
                    int nextIndex = stonePositions.get(nextPos);
                    if (canCrossMemo(stones, nextIndex, nextK, stonePositions, memo)) {
                        memo[index][k] = 1;
                        return true;
                    }
                }
            }
        }

        memo[index][k] = 0;
        return false;
    }
}
```
### 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`.

## Iterative Dynamic Programming with Hashing
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.
**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)`.
**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.
### Explanation
We use a `HashMap` where the keys are the stone positions and the values are `Set`s 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.

```java
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution {
    public boolean canCross(int[] stones) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int stone : stones) {
            map.put(stone, new HashSet<>());
        }
        
        // First jump is 1 unit from stone 0.
        // This requires a stone at position 1.
        if (!map.containsKey(1) || stones[1] != 1) {
            return false;
        }

        map.get(0).add(1);

        for (int i = 0; i < stones.length; i++) {
            int currentStone = stones[i];
            Set<Integer> jumps = map.get(currentStone);
            for (int k : jumps) {
                int nextPos = currentStone + k;
                if (nextPos == stones[stones.length - 1]) {
                    return true;
                }
                if (map.containsKey(nextPos)) {
                    Set<Integer> nextJumps = map.get(nextPos);
                    if (k - 1 > 0) {
                        nextJumps.add(k - 1);
                    }
                    nextJumps.add(k);
                    nextJumps.add(k + 1);
                }
            }
        }

        return false;
    }
}
```
### 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`.

# Solutions
### Java

```java
class 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 ; } }
```

### Python

```python
class 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 )
```

### CPP

```cpp
class 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 ); } };
```