Frog Jump

Frog Jump

What is this problem about?

The Frog Jump coding problem describes a frog trying to cross a river by jumping from stone to stone. The frog starts at stone 0. If the frog's last jump was k units, its next jump must be k-1, k, or k+1 units. The first jump must be exactly 1 unit. You are given an array of stone positions, and you need to determine if the frog can reach the last stone.

Why is this asked in interviews?

This is a "Hard" Dynamic Programming problem asked by companies like Amazon, Meta, and Snap. It tests your ability to define a complex state. The state isn't just "which stone am I on?", but "which stone am I on AND what was my last jump size?". It evaluates your ability to use Hash Maps to store DP states efficiently.

Algorithmic pattern used

This problem uses Dynamic Programming with Hash Maps.

1. Create a Hash Map where keys are the stone positions and values are Hash Sets. The set at map[stone] contains all the jump sizes that successfully brought the frog to that stone.
2. Initialize map[0] = {0} (or handle the first jump manually).
3. Iterate through each stone s.
4. For each jump size k in map[s], calculate the possible next jumps: k-1, k, k+1.
5. For each possible next jump j > 0, if s + j is a valid stone position in our map, add j to the set map[s + j].
6. If the set at the last stone is not empty, the frog can cross.

Example explanation

Stones: [0, 1, 3, 5, 6, 8, 12, 17]

1. Start at 0. First jump must be 1. Stone 1 exists. map[1] gets jump 1.
2. At stone 1, jump k=1. Next jumps: 0, 1, 2.
   • Jump 1 to 1+1=2 (Not a stone).
   • Jump 2 to 1+2=3 (Is a stone). map[3] gets jump 2.
3. At stone 3, jump k=2. Next jumps: 1, 2, 3.
   • Jump 2 to 3+2=5. map[5] gets jump 2.
   • Jump 3 to 3+3=6. map[6] gets jump 3. Continue this process. If 17 gets any jump value, return true.

Common mistakes candidates make

• 1D DP Array: Trying to use dp[i] = boolean, ignoring the fact that how you got to stone i dictates where you can go next.
• O(N^2) Array instead of Map: Using a 2D array dp[stone_index][jump_size] can work, but a Hash Map of Sets is often more intuitive and handles sparse stones better.
• First Jump Rule: Forgetting that the first jump is strictly 1 unit, not 0, 1, or 2.

Interview preparation tip

When the valid transitions from state A depend on the path taken to reach state A, your DP state must include that path information (in this case, the last_jump size).