Skip to content
← All posts

Frog Jump: Dynamic Programming with Jump States

5 min read
leetcodeproblemharddynamic-programming

A frog is crossing a river. The river is divided into units, and at some positions there are stones. The frog starts on the first stone (position 0) and wants to reach the last stone. On each turn, the frog can jump k-1, k, or k+1 units, where k is the size of its last jump. The first jump must be exactly 1 unit. Given the list of stone positions in sorted order, determine if the frog can reach the last stone.

This is LeetCode 403: Frog Jump, a hard-level problem that tests your ability to model state transitions in dynamic programming. The twist compared to simpler DP problems is that the state is not just "which stone am I on" but also "how big was the jump that got me here."

0135681217k=1k=2k=2k=3k=4k=5startgoal
One valid path across stones [0, 1, 3, 5, 6, 8, 12, 17]: jumps of 1, 2, 2, 3, 4, 5.

The approach: hash map of sets

The key insight is that each stone needs to track not just whether the frog can reach it, but which jump sizes can land there. A frog arriving at stone 5 with a jump of 2 has different future options than a frog arriving at stone 5 with a jump of 4. The jump size constrains the next move, so it is part of the state.

We use a hash map where each key is a stone position and each value is a set of jump sizes that can reach that stone. For every stone we process, we iterate through its set of jump sizes and propagate forward to stones reachable by jumps of k-1, k, and k+1.

  • Create a dictionary dp mapping each stone position to an empty set.
  • Initialize dp[0] = {0} to represent the starting state (the frog is at stone 0 with a "previous jump" of 0).
  • For each stone in order, for each jump size k in that stone's set, compute the three possible next positions: stone + k-1, stone + k, stone + k+1.
  • If a next position exists in the dictionary and the jump distance is positive, add that jump distance to the next stone's set.
  • After processing all stones, check if the last stone's set is non-empty.
def can_cross(stones):
    if stones[1] != 1:
        return False

    dp = {s: set() for s in stones}
    dp[0].add(0)

    for stone in stones:
        for k in dp[stone]:
            for jump in (k - 1, k, k + 1):
                if jump > 0 and stone + jump in dp:
                    dp[stone + jump].add(jump)

    return len(dp[stones[-1]]) > 0
Practice dynamic programming problems

Initialize: stone 0 has jump size {0} (starting position)

0{0}
1{}
3{}
5{}
6{}
8{}
12{}
17{}

The frog starts at stone 0. We record jump size 0 as the "last jump" to get here.

Process stone 0: k=0, so try k+1=1. Stone 0+1=1 exists. Add 1 to dp[1].

0{0}
1{1}
3{}
5{}
6{}
8{}
12{}
17{}

From stone 0 with k=0, only k+1=1 is valid (k-1 and k are 0). The frog can reach stone 1 with a jump of 1.

Process stone 1: k=1, try jumps 0,1,2. Stones 1,2,3. Stone 3 exists, add 2.

0{0}
1{1}
3{2}
5{}
6{}
8{}
12{}
17{}

k-1=0 (skip, not positive), k=1 targets stone 2 (not in set). k+1=2 targets stone 3 (exists). Add jump 2 to dp[3].

Process stone 3: k=2, try jumps 1,2,3. Targets 4,5,6. Stones 5 and 6 exist.

0{0}
1{1}
3{2}
5{2}
6{3}
8{}
12{}
17{}

Jump 1 targets 4 (missing). Jump 2 targets 5 (add 2 to dp[5]). Jump 3 targets 6 (add 3 to dp[6]).

Process stone 5: k=2, try 1,2,3. Targets 6,7,8. Stones 6 and 8 exist.

0{0}
1{1}
3{2}
5{2}
6{1,3}
8{3}
12{}
17{}

Jump 1 targets 6 (add 1 to dp[6]). Jump 2 targets 7 (missing). Jump 3 targets 8 (add 3 to dp[8]).

Process stone 6: k=1, try 1,2; k=3, try 2,3,4. Targets 7,8,9,10. Stone 8 exists.

0{0}
1{1}
3{2}
5{2}
6{1,3}
8{2,3}
12{}
17{}

Stone 6 has two jump sizes. k=3 reaches stone 8 via jump 2, stone 9 via 3, stone 10 via 4. Only 8 exists. Add 2 to dp[8].

Process stone 8: k=2 tries 1,2,3; k=3 tries 2,3,4. Stone 12 reached via k=3, jump 4.

0{0}
1{1}
3{2}
5{2}
6{1,3}
8{2,3}
12{4}
17{}

From k=3: targets 10,11,12. Only 12 exists (jump 4). From k=2: targets 9,10,11. None exist. dp[12] = {4}.

Process stone 12: k=4, try 3,4,5. Targets 15,16,17. Stone 17 exists!

0{0}
1{1}
3{2}
5{2}
6{1,3}
8{2,3}
12{4}
17{5}

Jump 5 lands on stone 17, the last stone. dp[17] is non-empty, so the frog can cross. Return true.

Drill this pattern with spaced repetition

Complexity

TimeSpace
Hash map of setsO(n^2)O(n^2)

Each stone can accumulate at most O(n) different jump sizes (since jumps grow roughly linearly and there are n stones). We process each stone and iterate through its jump sizes, giving O(n^2) total work in the worst case. The space is also O(n^2) because the sets across all stones can hold up to O(n^2) entries total.

In practice, the sets tend to be much smaller. Most stones will only have a handful of reachable jump sizes, so the algorithm runs faster than the worst case on typical inputs.

The building blocks

Hash map as DP table: Instead of a flat array, we use a dictionary keyed by stone position. This lets us skip positions where no stone exists, which is critical when stone positions can be spread far apart (up to 2^31 - 1). The same pattern appears in problems like Word Break where valid positions are sparse.

State = position + additional context: Many DP problems require tracking more than just position. Here the "additional context" is the jump size. You see the same idea in Best Time to Buy and Sell Stock III where state includes the number of transactions, and in House Robber II where state includes whether you picked the first house.

Forward propagation: Instead of looking backward to fill each cell (like Coin Change), we look forward from each cell to push reachable states. Both directions work for DP, but forward propagation feels more natural here because the next positions depend on the current jump size.

Edge cases

  • Second stone is not at position 1: The first jump must be exactly 1 unit, so if stones[1] != 1, return false immediately.
  • Only two stones [0, 1]: The frog jumps 1 unit and lands on the last stone. Return true.
  • Gaps too large to bridge: If stones are spaced so far apart that no valid sequence of k-1, k, k+1 jumps can reach them, the last stone's set stays empty.
  • Adjacent stones with many paths: Some configurations allow the frog to reach the same stone with many different jump sizes, which is fine - the set handles deduplication automatically.

From understanding to recall

The Frog Jump problem looks intimidating at first because of the "hard" label, but the core mechanic is something you have seen before: propagate reachable states forward through a sequence of positions. The only new piece is that the state includes the jump size, not just the position.

If you can solve Climbing Stairs, you already understand the idea of "from this position, what positions can I reach next?" Frog Jump adds a second dimension to that question by making the set of reachable positions depend on how you arrived. Once you internalize that pattern - "my future options depend on my current state, not just my current position" - you can apply it to any problem where transitions carry context.

Spaced repetition helps you lock in the specific implementation details: using a hash map of sets, the triple loop over k-1, k, k+1, and the early exit when the second stone is not at position 1. These are the details that slip away between practice sessions unless you actively revisit them.

Related posts

  • Coin Change - Classic bottom-up DP where you iterate through choices at each state, same fundamental pattern with a simpler state model
  • Climbing Stairs - The simplest forward-propagation DP problem, a great warm-up before tackling the extra state dimension in Frog Jump
  • Longest Increasing Subsequence - Another DP problem where the transition depends on context (the last value chosen), building the same intuition for multi-dimensional state
Try CodeBricks free