Frog Jump — Hard Problem & Solution

A frog crosses a river on stones at the positions listed in stones (strictly increasing, starting at 0).

Difficulty: Hard
Topics: Arrays, Hash Table, Dynamic Programming
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A frog crosses a river on stones at the positions listed in stones (strictly increasing, starting at 0). It begins on the first stone and its first jump must be 1 unit.

If the last jump was k units, the next must be k - 1, k or k + 1 units, always forwards. Return whether the frog can reach the last stone.

Example 1

Input: stones = [0,1,3,5,6,8,12,17]
Output: true
Explanation: Jumps of 1, 2, 2, 3, 4 and 5 reach the end.

Example 2

Input: stones = [0,1,2,3,4,8,9,11]
Output: false
Explanation: The gap from 4 to 8 is too wide for the jump built up so far.

Example 3

Input: stones = [0,1]
Output: true

Constraints

2 <= stones.length <= 1000
0 <= stones[i] <= 1000000000
stones[0] == 0
stones is sorted strictly increasing.

How to solve Frog Jump

Forward reachability over states (stone, lastJump). From each reachable state, try the three legal jump sizes and mark the landing stone reachable with that size.

Approach

Map each stone position to its index for constant-time landing checks.
Seed stone 0 with jump size 0, so the only legal first move is size 1.
For each stone in order, for each recorded jump size k, try k-1, k and k+1, skipping non-positive sizes.
The frog can cross when the last stone has any recorded jump size.

Why it works

The next legal jumps depend only on the size of the jump just made, so (stone, lastJump) is a sufficient state. Processing stones left to right is safe because every jump moves strictly forwards, so a state is finalised before it is used. The jump size never exceeds the number of stones, which bounds the state space.

Complexity

Time — O(n²)
Space — O(n²)

Pitfalls

Tracking only the stone, not the jump size, loses the information the rules depend on.
A jump of size 0 or less is illegal and must be skipped — seeding stone 0 with 0 is what forces the first jump to be 1.
The landing must be exactly on a stone; there is no partial progress.

Reference solution

Python

from typing import List

def canCross(stones: List[int]) -> bool:
    n = len(stones)
    pos = {s: i for i, s in enumerate(stones)}
    dp = [set() for _ in range(n)]
    dp[0].add(0)
    for i in range(n):
        for k in list(dp[i]):
            for step in (k - 1, k, k + 1):
                if step <= 0:
                    continue
                nxt = stones[i] + step
                if nxt in pos:
                    dp[pos[nxt]].add(step)
    return len(dp[n - 1]) > 0

JavaScript

var canCross = function(stones) {
    var n = stones.length;
    var pos = {}, i;
    for (i = 0; i < n; i++) pos[stones[i]] = i;
    var dp = [];
    for (i = 0; i < n; i++) dp.push({});
    dp[0][0] = true;
    for (i = 0; i < n; i++) {
        var keys = Object.keys(dp[i]);
        for (var t = 0; t < keys.length; t++) {
            var k = Number(keys[t]);
            var steps = [k - 1, k, k + 1];
            for (var q = 0; q < 3; q++) {
                var step = steps[q];
                if (step <= 0) continue;
                var nxt = stones[i] + step;
                if (pos[nxt] !== undefined) dp[pos[nxt]][step] = true;
            }
        }
    }
    return Object.keys(dp[n - 1]).length > 0;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue