Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

LeetCode 403 - Frog Jump

Problem Understanding

The problem describes a frog trying to cross a river by jumping across stones placed at specific positions. The input array stones contains the positions of all stones in sorted ascending order. The frog starts on the first stone, which is always at position 0.

The frog does not move arbitrarily. Its movement is constrained by the size of its previous jump. The first jump must be exactly 1 unit. After that, if the previous jump length was k, then the next jump length can only be one of:

k - 1
k
k + 1

Additionally, the frog can only move forward, and it may only land on existing stones. If a jump lands in the water, that path is invalid.

The task is to determine whether the frog can eventually land on the final stone in the array.

The constraints are important because they strongly influence which algorithms are feasible:

stones.length <= 2000
Stone positions can be very large, up to 2^31 - 1
Stones are strictly increasing

A brute-force recursive search would explore many repeated states and quickly become exponential. Since there can be up to 2000 stones, we need a more efficient approach that avoids recomputing the same possibilities repeatedly.

Several edge cases are important:

The second stone must be at position 1, otherwise the frog cannot make its mandatory first jump.
Large gaps between stones may make crossing impossible.
Multiple jump lengths may lead to the same stone, which means state reuse is important.
The frog may revisit the same stone with different jump lengths, and those represent different states.

The critical observation is that the frog's state is not determined only by its current position, but also by the size of the last jump used to reach that position.

Approaches

Brute Force Approach

A straightforward solution is to use recursive backtracking. From each stone, try all valid next jumps:

k - 1
k
k + 1

For every valid jump, recursively continue from the destination stone.

This approach is correct because it explores every possible sequence of jumps. If any path reaches the final stone, the answer is true.

However, this solution is far too slow. The same states get recomputed repeatedly. For example, the frog may reach the same stone with the same jump length through multiple different paths. Without memoization, the recursion tree grows exponentially.

Key Insight

The important insight is that the problem contains overlapping subproblems.

A state can be represented as:

(current stone position, last jump length)

If we already know whether a particular state can reach the end, we should not recompute it again.

This naturally leads to dynamic programming.

A very effective DP formulation is:

For each stone, store all jump lengths that can land on it.

If the frog reaches a stone using jump length k, then from that stone it may attempt jumps of:

k - 1
k
k + 1

Whenever one of those jumps lands on another valid stone, we record that new jump length for the destination stone.

This transforms the problem from exponential exploration into a bounded state traversal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(3^n) worst case	O(n) recursion stack	Explores all jump combinations recursively
Optimal Dynamic Programming	O(n²)	O(n²)	Stores reachable jump lengths for each stone

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

Create a set containing all stone positions.

This allows constant-time lookup to determine whether a jump lands on a valid stone. 2. Create a hash map where each stone maps to a set of jump lengths that can reach it.

For example:

reachable[5] = {2,3}

means the frog can land on stone 5 using jumps of length 2 or 3. 3. Initialize the starting state.

The frog starts at position 0, and the first jump must be 1. Therefore:

reachable[0] = {0}

The 0 jump is just a placeholder representing the starting state. 4. Iterate through each stone in order.

For every jump length that can reach the current stone, calculate the next possible jump lengths:

jump - 1
jump
jump + 1

Ignore non-positive jumps.

A jump length of 0 or negative is invalid because the frog must move forward. 6. Compute the next stone position.

next_position = current_stone + next_jump

If the destination exists in the stone set, record the jump length.

reachable[next_position].add(next_jump)

This means the frog can now reach that stone using that jump size. 8. Continue processing until all reachable states are explored. 9. At the end, check whether the final stone has any reachable jump lengths stored.

If its set is non-empty, the frog can cross the river.

Why it works

The algorithm maintains the invariant that every stored (stone, jump) pair represents a valid way for the frog to reach that stone using exactly that jump length.

From every valid state, the algorithm generates all legal next states according to the problem rules. Since every reachable state is explored exactly once per jump length, the algorithm eventually discovers all possible valid paths.

If the final stone receives at least one reachable jump length, then there exists a valid sequence of jumps that crosses the river.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        if stones[1] != 1:
            return False

        stone_set = set(stones)

        reachable = defaultdict(set)
        reachable[0].add(0)

        for stone in stones:
            for jump in reachable[stone]:
                for next_jump in (jump - 1, jump, jump + 1):
                    if next_jump <= 0:
                        continue

                    next_stone = stone + next_jump

                    if next_stone in stone_set:
                        reachable[next_stone].add(next_jump)

        return len(reachable[stones[-1]]) > 0

The implementation begins with an important optimization:

if stones[1] != 1:
    return False

Since the first jump must be exactly 1, the second stone must be located at position 1. If it is not, the answer is immediately False.

The stone_set provides constant-time membership checks. Without it, checking whether a destination stone exists would require linear searching.

The reachable dictionary maps each stone position to the set of jump lengths that can reach it. Using sets prevents duplicate states from being stored repeatedly.

The outer loop processes stones in ascending order. For each reachable jump size, the algorithm generates the three allowed next jumps. Invalid non-positive jumps are skipped.

Whenever a valid destination stone exists, the corresponding jump length is recorded for that stone.

Finally, the algorithm checks whether the last stone has at least one reachable jump length.

Go Solution

func canCross(stones []int) bool {
	if stones[1] != 1 {
		return false
	}

	stoneSet := make(map[int]bool)
	for _, stone := range stones {
		stoneSet[stone] = true
	}

	reachable := make(map[int]map[int]bool)

	for _, stone := range stones {
		reachable[stone] = make(map[int]bool)
	}

	reachable[0][0] = true

	for _, stone := range stones {
		for jump := range reachable[stone] {
			for nextJump := jump - 1; nextJump <= jump+1; nextJump++ {
				if nextJump <= 0 {
					continue
				}

				nextStone := stone + nextJump

				if stoneSet[nextStone] {
					reachable[nextStone][nextJump] = true
				}
			}
		}
	}

	return len(reachable[stones[len(stones)-1]]) > 0
}

The Go implementation follows the same logic as the Python version, but there are some language-specific differences.

Go does not have a built-in set type, so maps with boolean values are used to simulate sets:

map[int]bool

The nested structure:

map[int]map[int]bool

represents:

stone -> set of jump lengths

Unlike Python's defaultdict, Go requires explicit initialization of nested maps before inserting values.

Integer overflow is not a concern here because the constraints fit comfortably within Go's int type on LeetCode environments.

Worked Examples

Example 1

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

Initial state:

Stone	Reachable Jumps
0	{0}

Process stone 0:

Jump options from 0 are -1, 0, 1
Only 1 is valid
Stone 1 exists

Update:

Stone	Reachable Jumps
0	{0}
1	{1}

Process stone 1:

From jump 1:

Next jumps: 0, 1, 2
Valid positive jumps: 1, 2

Stone 2 does not exist.

Stone 3 exists.

Update:

Stone	Reachable Jumps
3	{2}

Process stone 3:

From jump 2:

Next jumps: 1, 2, 3

Stone 4 does not exist.

Stone 5 exists.

Stone 6 exists.

Update:

Stone	Reachable Jumps
5	{2}
6	{3}

Process stone 5:

From jump 2:

Next jumps: 1, 2, 3

Stone 6 exists.

Stone 7 does not exist.

Stone 8 exists.

Update:

Stone	Reachable Jumps
6	{1,3}
8	{3}

Process continues similarly until:

Stone	Reachable Jumps
17	{5}

Since the final stone has reachable jumps, return true.

Example 2

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

The frog can successfully reach stone 4, but after that:

Maximum possible next jump is too small
Gap from 4 to 8 is 4
The reachable jump lengths at 4 do not allow a jump of 4

Eventually, no new states are generated.

Final state:

Stone	Reachable Jumps
11	{}

Since the final stone has no reachable jump lengths, return false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Each stone may store up to O(n) reachable jump lengths
Space	O(n²)	The DP structure may contain O(n²) state pairs

In the worst case, every stone can be reached with many different jump lengths. Since there are n stones and each may store up to n jump values, the total number of states is bounded by O(n²).

Each state is processed once, and each processing step considers only three transitions, so the total runtime remains O(n²).

Test Cases

solution = Solution()

assert solution.canCross([0,1,3,5,6,8,12,17]) == True
# Standard successful crossing example

assert solution.canCross([0,1,2,3,4,8,9,11]) == False
# Large unreachable gap

assert solution.canCross([0,1]) == True
# Smallest possible successful input

assert solution.canCross([0,2]) == False
# First jump must be exactly 1

assert solution.canCross([0,1,3,6,10,15,21,28]) == True
# Increasing jump sizes every time

assert solution.canCross([0,1,2,3,5,6,8,12,17]) == True
# Multiple valid paths

assert solution.canCross([0,1,3,4,5,7,9,10,12]) == True
# Dense reachable stones

assert solution.canCross([0,1,3,7]) == False
# Gap becomes too large

assert solution.canCross([0,1,2,4,7,11]) == False
# Reachable early, impossible later

assert solution.canCross([0,1,3,5,6,8,9,11]) == True
# Requires careful jump tracking

Test	Why
`[0,1,3,5,6,8,12,17]`	Standard successful example
`[0,1,2,3,4,8,9,11]`	Standard impossible example
`[0,1]`	Smallest successful case
`[0,2]`	Invalid first jump
`[0,1,3,6,10,15,21,28]`	Consecutive increasing jumps
`[0,1,2,3,5,6,8,12,17]`	Multiple reachable states
`[0,1,3,4,5,7,9,10,12]`	Dense graph of transitions
`[0,1,3,7]`	Early dead end
`[0,1,2,4,7,11]`	Failure after several successful jumps
`[0,1,3,5,6,8,9,11]`	Multiple jump choices at many stones

Edge Cases

Missing Stone at Position 1

The first jump must be exactly 1. If the second stone is not located at position 1, the frog immediately fails.

Example:

[0,2]

A naive implementation might still begin recursive exploration, but this is unnecessary work. The implementation handles this efficiently with an early return:

if stones[1] != 1:
    return False

Large Gaps Between Stones

A large gap may become impossible to cross because jump sizes can only change gradually.

Example:

[0,1,2,3,4,8]

Even though the frog reaches stone 4, it cannot suddenly jump 4 units because its previous jumps are too small.

The DP approach naturally handles this because unreachable states are never added to the table.

Multiple Ways to Reach the Same Stone

A stone may be reachable using different jump lengths, and those represent different future possibilities.

Example:

[0,1,3,5,6,8]

Stone 6 may be reached using different jump sizes. A buggy implementation that stores only whether a stone is reachable would lose critical information.

The solution correctly stores all reachable jump lengths for every stone:

reachable[stone] = set(...)

This preserves all future movement possibilities and guarantees correctness.