Skip to main content

403. Frog Jump

hard

A frog crosses a river of stones, with jump sizes constrained by its previous jump (k, k-1, k+1). DP keyed by (position, last jump size) — the textbook 2D state problem with sparse keys.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water. Given a list of stones' positions (in units) in sorted ascending order, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit. If the frog's last jump was k units, its next jump must be either k - 1, k, or k + 1 units. The frog can only jump in the forward direction.

Constraints

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

Examples

Example 1

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

Explanation: Jumps of size 1, 2, 2, 3, 4, 5 land on every stone and reach 17.

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

State = (current stone, last jump size). At each stone, branch into k-1, k, k+1.

Hint 2

Use a hash map: position -> set of last-jump sizes reachable at that position.

Hint 3

If stones[1] != 1 the frog can't even leave stone 0.

Solution approach

Reveal approach

Define the subproblem reach[pos] = the set of last-jump sizes k such that the frog can land on position pos with its previous jump being k. The recurrence relation: from (pos, k), the frog can jump to positions pos + (k-1), pos + k, pos + (k+1) provided each target is a stone and the new jump size is positive. Implement reach as a hash map keyed by stone position with a set of jump sizes as the value. Initialize reach[0] = {0} (the frog starts on stone 0 with no prior jump; we'll require the first jump to be exactly 1). Iterate stones left-to-right; for each stone pos in reach, for each k in reach[pos], for each delta in {-1, 0, 1} with newK = k + delta and newK > 0, if pos + newK is a stone insert newK into reach[pos + newK]. Return whether reach[stones[stones.length - 1]] is non-empty. Time O(n^2) in the worst case (each stone reachable by O(n) different jump sizes), space O(n^2). The sparse map keeps real-world runs much faster.

Complexity

Time
O(n^2)
Space
O(n^2)

Related patterns

  • dynamic-programming
  • memoization-recursion
  • hash-map

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon

Practice these live with InterviewChamp.AI

Drill Frog Jump and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →