Problem Statement

Frog Jump

A frog wants to cross a river by hopping on stones. You are given the positions of the stones along the river, like marks on a ruler. The frog starts on the first stone and wants to reach the last one. Here is the catch: the size of each jump depends on the jump before it. If the last hop covered k units, the next hop can be k-1, k, or k+1 units, and never less than 1. The very first hop must be exactly 1 unit. We need to answer yes or no: can the frog make it all the way across? To do this we use a hash map. A hash map is like a labeled set of boxes: you look something up by its name and instantly get what is inside. Here each stone gets its own box, and inside that box we keep the set of jump sizes that could have landed the frog on that stone. We track jump sizes (not just "can I reach it") because the next legal hop depends on how big the last hop was.

hardDynamic ProgrammingDynamic ProgrammingTime: O(n²) · Space: O(n²)

Signals to notice

frog jumping on stonesnext jump depends on last jumpstate = (position, last jump size)

Brute force first

Try all jump sequences — exponential.

The key insight

Map each stone to set of reachable jump sizes. For each (stone, k): try k-1, k, k+1 to next stones. O(n²).

Trace it on `stones = [0,1,3,5,6,8,12,17]`

init dp[0]={0}, all others empty
stone 0, k=0: jump 1 lands on 1 -> dp[1]={1}
stone 1, k=1: jump 2 lands on 3 -> dp[3]={2}
stone 3, k=2: jump 2->5, jump 3->6 -> dp[5]={2}, dp[6]={3}
stone 5, k=2: jump 1->6, jump 3->8 -> dp[6]={3,1}, dp[8]={3}
stone 6, k in {3,1}: reaches 8 -> dp[8]={3,2}
stone 8, k in {3,2}: jump 4->12 -> dp[12]={4}
stone 12, k=4: jump 5->17 -> dp[17]={5}; dp[17] non-empty -> return true

What must stay true

State = (position, last jump). Same position with different last jumps has different options. Set per stone avoids duplicates.

Shape of the loop

dp = {stone: empty set for each stone}; dp[first].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) is a stone:
                dp[stone + jump].add(jump)
return dp[last stone] is non-empty

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not tracking jump size — options depend on how you arrived, not just where you are.

Dynamic Programming Pattern