AlgoMaster Logo

Frog Jump

hardFrequencyUpdated September 21, 2026

Understanding the Problem

We have a frog sitting on stone 0, and it needs to reach the last stone in the array. The catch is that the frog's jump size is constrained by its previous jump. If the last jump was k units, the next jump can only be k - 1, k, or k + 1 units. The first jump is always exactly 1 unit.

This means the frog's state at any point is not only "which stone am I on?" but also "how big was my last jump?" Two different paths to the same stone can lead to different futures depending on the jump size that got the frog there. Arriving at stone 5 with a last jump of 2 differs from arriving with a last jump of 4, because the set of reachable next stones changes.

That dual-state nature, position plus last jump size, is what points this problem toward dynamic programming. The state is the pair (stone, last jump), not the stone alone.

Key Constraints:

  • 2 <= stones.length <= 2000 → With n up to 2000, an O(n^2) solution does about 4 million operations, well within limits. A DP with a state for each (stone, jump size) pair is feasible.
  • stones[0] == 0 and stones is sorted → No sorting needed. The frog always starts at position 0.
  • 0 <= stones[i] <= 2^31 - 1 → Stone positions span the full 32-bit range, but there are at most 2000 of them. A position-indexed array is out of the question, so a hash structure keyed by position handles the "is there a stone here?" lookup in O(1).

Approach 1: DFS with Memoization (Top-Down DP)

Intuition

The problem maps directly onto recursion. The frog is at some stone with a last jump of size k, and from there it can try jumping k-1, k, or k+1 units forward. If the destination has a stone, recurse from there. If any path reaches the last stone, return true.

Without memoization this is exponential, because the same (stone, jump size) state can be reached through many different paths and gets re-explored each time. The outcome from a given state depends only on that state, not on the path taken to reach it, so we can cache which states have already been explored and skip them on later visits.

To check whether a position has a stone in O(1), we store all stone positions in a hash set. Positions reach 2^31, so an array indexed by position is not an option.

Algorithm

  1. Store all stone positions in a hash set for O(1) lookup.
  2. Keep a hash set of explored (position, jump) states. If the current state is already in it, return false: a state that failed once fails on every revisit, since the outcome depends only on the state.
  3. Starting from position 0 with last jump 0, try jumps of size k-1, k, and k+1, where k is the last jump size.
  4. Skip any jump that is <= 0, since the frog cannot jump backward or stay in place.
  5. If the destination has a stone, recurse from there. Reaching the last stone returns true.
  6. If no jump leads to a solution, return false.

Example Walkthrough

1Start DFS at pos=0, k=0. Try jump 1
0
0
pos=0
1
1
2
3
3
5
4
6
5
8
6
12
7
17
1/7

Code

The next approach removes the recursion and processes states in forward order, which sidesteps the function-call overhead and the state-encoding key.

Approach 2: Bottom-Up DP with Hash Map

Intuition

Instead of exploring paths from the start and recursing toward the end, the bottom-up version flips the perspective: for each stone, track every jump size that can land on it, then push each of those forward to the stones it can reach.

Maintain a map from each stone position to the set of jump sizes that can reach it. Initialize stone 0 with jump size 0, since the frog starts there with no prior jump. Process the stones left to right. For each stone at position p with a reachable jump size k, the frog can try jumps of k-1, k, and k+1. If position p + jump has a stone, add jump to that stone's set of reachable jump sizes.

If the last stone's set is non-empty after processing every stone, some path reaches it.

Algorithm

  1. Create a hash map where each key is a stone position and the value is a set of jump sizes that can reach that stone.
  2. Initialize: map stone 0 with the set {0}.
  3. For each stone position p in order:
    • For each jump size k in the set for stone p:
      • For each next jump size jump in {k-1, k, k+1}:
        • If jump > 0 and position p + jump exists in the map, add jump to the set at position p + jump.
  4. Return whether the last stone's set is non-empty.

Example Walkthrough

1Initialize: frog starts at stone 0 (pos=0), jumps={0}
0
0
process
1
1
2
3
3
5
4
6
5
8
6
12
7
17
1/9

Code

Both approaches are O(n^2), and the worst case cannot be improved asymptotically. The next approach keeps the same algorithm but adds an early exit and a linear pre-check that rejects impossible inputs before building the map.

Approach 3: Optimized Bottom-Up DP with Early Exit

Intuition

The core algorithm matches Approach 2, with two optimizations that improve the average case.

The first is a validity pre-check. If stones[1] != 1, the frog can never leave the first stone, because the first jump must be exactly 1 unit. The check generalizes: if any gap between consecutive stones exceeds the largest jump the frog could have built up by that point, the input is impossible and we return false right away.

Bounding that maximum jump comes from how jump sizes grow. The frog's first jump is size 1, and each jump can grow by at most 1. To reach stone index i, the frog has taken i jumps, so its jump size on arrival is at most i. The next jump can therefore be at most i + 1, which means a gap stones[i+1] - stones[i] larger than i + 1 can never be bridged.

The second optimization is early termination: the moment a jump lands on the last stone, return true without processing the remaining stones.

Algorithm

  1. Quick check: if stones[1] != 1, return false immediately.
  2. Quick check: for each consecutive pair, if stones[i+1] - stones[i] > i + 1, return false (gap too large for any possible path).
  3. Create a hash map from stone position to set of reachable jump sizes.
  4. Initialize stone 0 with jump size 0.
  5. For each stone, propagate jumps forward. If any jump reaches the last stone, return true immediately.
  6. If we finish processing all stones without reaching the last, return false.

Example Walkthrough

1Pre-check: stones[1]=1, so the first jump is valid
0
0
1
1
==1 ok
2
3
3
5
4
6
5
8
6
12
7
17
1/9

Code