LeetCode 403: Frog Jump

Problem Restatement

A frog wants to cross a river by jumping on stones.

The stones are given as a sorted array:

stones

Each value in stones is a position on the river.

The frog starts on the first stone, which is always position 0.

The first jump must be exactly 1 unit.

After that, if the frog’s previous jump was k units, then the next jump must be one of:

k - 1
k
k + 1

The frog can only jump forward, and it can land only on stones.

Return True if the frog can reach the last stone. Otherwise, return False.

Input and Output

Constraints include 2 <= stones.length <= 2000, stones[0] == 0, and the stones are strictly increasing. The problem statement specifies the first jump rule and the k - 1, k, k + 1 transition rule.

Examples

Consider:

stones = [0, 1, 3, 5, 6, 8, 12, 17]

The answer is:

True

One valid path is:

0 -> 1 -> 3 -> 5 -> 8 -> 12 -> 17

The jump lengths are:

1, 2, 2, 3, 4, 5

Each jump follows the rule. After a jump of 2, the next jump can be 1, 2, or 3. After a jump of 3, the next jump can be 2, 3, or 4.

Now consider:

stones = [0, 1, 2, 3, 4, 8, 9, 11]

The answer is:

False

The frog can reach stone 4, but the next stone is 8. The gap is too large for the jump sizes available at that point. This matches the standard example for the problem.

First Thought: Backtracking

A direct way is to try every possible jump.

From a stone, if the previous jump was k, recursively try:

k - 1
k
k + 1

If one of those jumps lands on another stone, continue from there.

This matches the problem naturally.

The state is:

current stone position
last jump length

But plain recursion repeats many states.

For example, the frog may reach the same stone with the same previous jump through different paths. Once that state has been solved, solving it again wastes time.

So we add memoization.

Key Insight

The frog’s future depends only on two values:

stone index
last jump length

It does not matter how the frog reached that state.

If the frog is on stone i and the previous jump was k, then the possible next jumps are fully determined:

k - 1, k, k + 1

So we can define a dynamic programming state:

dfs(i, k)

Meaning:

Can the frog reach the last stone if it is currently on stone i and its previous jump length was k?

To quickly check whether a target landing position exists, store all stone positions in a hash map:

position -> index

Algorithm

Create a dictionary pos mapping each stone position to its index.

Then define a memoized DFS:

dfs(i, k)

where:

For each state:

1. If i is the last stone index, return True.
2. Try next jump lengths k - 1, k, and k + 1.
3. Ignore non-positive jump lengths.
4. Let the next stone position be stones[i] + jump.
5. If that position exists, recursively test that next state.
6. If any recursive call returns True, return True.
7. Otherwise, return False.

The first call is:

dfs(0, 0)

This works because the first valid next jump from 0 is 1.

From k = 0, the possible next jumps are:

-1, 0, 1

Only 1 is positive, so the first jump rule is enforced naturally.

Correctness

We prove that dfs(i, k) returns True exactly when the frog can reach the last stone from stone i after making a previous jump of length k.

If i is the last stone index, the frog has already reached the goal, so dfs(i, k) correctly returns True.

Otherwise, the frog’s next jump must be one of k - 1, k, or k + 1. The algorithm checks exactly these three jump lengths. It rejects non-positive jumps because the frog can only move forward.

For each valid jump length, the algorithm computes the landing position. If that position exists in the stone map, then the jump is legal. The recursive call tests whether the frog can reach the last stone after making that jump.

If any legal next jump can eventually reach the last stone, the algorithm returns True.

If none of the legal next jumps can reach the last stone, then every possible move from this state fails, so the algorithm returns False.

Memoization only stores already computed results for the same (i, k) state. Since the answer for a state depends only on i and k, memoization does not change correctness.

Therefore, the initial call returns True exactly when the frog can cross the river.

Complexity

Here n is the number of stones.

The number of stones is at most 2000, so an O(n^2) dynamic programming solution is acceptable.

Implementation

from functools import cache
from typing import List

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        pos = {stone: i for i, stone in enumerate(stones)}
        n = len(stones)

        @cache
        def dfs(i: int, k: int) -> bool:
            if i == n - 1:
                return True

            for jump in (k - 1, k, k + 1):
                if jump <= 0:
                    continue

                next_pos = stones[i] + jump

                if next_pos in pos:
                    if dfs(pos[next_pos], jump):
                        return True

            return False

        return dfs(0, 0)

Code Explanation

We first build a fast lookup table:

pos = {stone: i for i, stone in enumerate(stones)}

This lets us check whether a landing position is a stone in expected constant time.

Then we define:

dfs(i, k)

This means the frog is currently on stones[i], and the previous jump length was k.

The base case is:

if i == n - 1:
    return True

If the frog is on the last stone, it has crossed the river.

Then we try the three allowed next jump lengths:

for jump in (k - 1, k, k + 1):

We skip invalid jumps:

if jump <= 0:
    continue

Then we compute the next landing position:

next_pos = stones[i] + jump

If that position is a stone, we recurse:

if next_pos in pos:
    if dfs(pos[next_pos], jump):
        return True

If none of the possible jumps works, this state fails:

return False

Finally, we start at stone 0 with previous jump length 0:

return dfs(0, 0)

Testing

def test_frog_jump():
    s = Solution()

    assert s.canCross([0, 1, 3, 5, 6, 8, 12, 17]) is True
    assert s.canCross([0, 1, 2, 3, 4, 8, 9, 11]) is False
    assert s.canCross([0, 1]) is True
    assert s.canCross([0, 2]) is False
    assert s.canCross([0, 1, 2]) is True
    assert s.canCross([0, 1, 3, 6, 10, 15, 21]) is True
    assert s.canCross([0, 1, 3, 6, 10, 13, 15, 18]) is True

    print("all tests passed")

Test Notes