#403

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Frog Jump

Determine if a frog can cross a river using jumps constrained by previous step sizes in a dynamic programming state transition.

array dynamic programming

Problem Statement

A frog is attempting to cross a river represented by a series of stones at increasing unit positions. The frog starts on the first stone and can only move forward, jumping a variable number of units determined by its previous jump.

If the frog's last jump was k units, the next jump must be k-1, k, or k+1 units. Given a sorted array of stone positions, determine whether the frog can reach the last stone by landing only on stones, never in water, starting with a first jump of 1 unit.

Examples

Example 1

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

Output: true

The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.

Example 2

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

Output: false

There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.

Constraints

2 <= stones.length <= 2000
0 <= stones[i] <= 231 - 1
stones[0] == 0
stones is sorted in a strictly increasing order.

Solution Approach

Dynamic Programming with State Tracking

Define a DP table or hash map where each stone position maps to a set of jump sizes that can reach it. Iterate over stones, updating reachable jumps based on k-1, k, and k+1 moves, ensuring only forward jumps to existing stones are considered.

Pruning Impossible Paths

Skip any jump that would land in a position without a stone. This prevents exponential exploration of invalid paths and optimizes the DP by only maintaining feasible jumps that can eventually reach the last stone.

Final Stone Verification

After filling the DP states, check if the set of reachable jumps at the last stone is non-empty. If yes, return true; otherwise, return false. This confirms whether any valid sequence of jumps allows the frog to cross the river.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity varies with the number of stones and reachable jumps per stone; in the worst case, it can approach O(n^2). Space complexity is O(n*m) where m is the average number of jumps stored per stone.

What Interviewers Usually Probe

Can you model this problem as a state transition dynamic programming scenario?
What data structure can efficiently track reachable positions with jump constraints?
How do you prune moves that cannot possibly lead to the last stone?

Common Pitfalls or Variants

Common pitfalls

Assuming constant jump sizes instead of k-1, k, k+1 transitions.
Neglecting to check if a jump lands on a valid stone before updating states.
Failing to initialize the first jump correctly at 1 unit, causing early DP failure.

Follow-up variants

Determine the minimum number of jumps needed to reach the last stone using the same k-1, k, k+1 rule.
Return all possible sequences of jumps that allow the frog to reach the last stone.
Allow backward jumps under specific constraints and adapt the DP accordingly.

FAQ

What pattern is used to solve Frog Jump efficiently?

State transition dynamic programming is used, modeling each stone with reachable jump sizes.

Why can't I just iterate sequentially through stones?

Sequential iteration ignores variable jump constraints; the frog's next move depends on the previous jump size.

Can the frog skip stones in Frog Jump?

No, jumps must land exactly on stones; jumping into the river is invalid.

What is the first jump size for the frog?

The first jump is always 1 unit from the starting stone.

How does GhostInterview help with this problem?

It provides step-by-step state management, pruning strategies, and verifies if the last stone is reachable using DP transitions.

terminal

Solution

Solution 1: Hash Table + Memoization

We use a hash table $pos$ to record the index of each stone. Next, we design a function $dfs(i, k)$, which means that the frog jumps from the $i$-th stone and the last jump distance is $k$. If the frog can reach the end, the function returns `true`, otherwise it returns `false`.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        @cache
        def dfs(i, k):
            if i == n - 1:
                return True
            for j in range(k - 1, k + 2):
                if j > 0 and stones[i] + j in pos and dfs(pos[stones[i] + j], j):
                    return True
            return False

        n = len(stones)
        pos = {s: i for i, s in enumerate(stones)}
        return dfs(0, 0)

Solution 2: Dynamic Programming

We define $f[i][k]$ to be true if and only if it is possible to reach stone $i$ with last jump of size $k$. Initially $f[0][0] = true$, and all other elements of $f$ are false.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        @cache
        def dfs(i, k):
            if i == n - 1:
                return True
            for j in range(k - 1, k + 2):
                if j > 0 and stones[i] + j in pos and dfs(pos[stones[i] + j], j):
                    return True
            return False

        n = len(stones)
        pos = {s: i for i, s in enumerate(stones)}
        return dfs(0, 0)

Continue Practicing

#396 rotate function #410 split array largest sum #413 arithmetic slices