Frog Jump

Hard Dynamic Programming 1D DP Original on LeetCode

Reported atFlipkart

Frog Jump is a hard dynamic programming problem solved with the 1d dp pattern. The best approach, optimal (jump sizes per stone), runs in O(n²) time and O(n²) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every jump sequence) up.

Problem

A frog wants to cross a river by hopping on stones. You are given stones, the positions of the stones in strictly increasing order; the frog starts on the first stone (position 0) and must finish on the last one. It can only land on stones, never in the water.

The first jump must be exactly 1 unit. After a jump of length k, the next jump must have length k - 1, k or k + 1, and the frog only moves forward (jump lengths are positive).

Return true if the frog can reach the last stone, otherwise false.

Examples

Example 1

Input
stones = [0, 1, 2, 4, 7, 11]
Output
true
Why
Jump sizes 1, 1, 2, 3, 4 take the frog 0 → 1 → 2 → 4 → 7 → 11; each jump differs from the previous one by at most 1.

Example 2

Input
stones = [0, 1, 3, 7, 8]
Output
false
Why
From 1 (last jump 1) the frog can reach 3 with a jump of 2, but from 3 it can jump at most 3 and lands on 4, 5 or 6, none of which is a stone.

Example 3

Input
stones = [0, 2]
Output
false
Why
The very first jump must have size exactly 1, so position 2 cannot be reached.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every jump sequence)O(3^n)O(n)
Optimal (jump sizes per stone)O(n²)O(n²)

1Brute force (try every jump sequence)

TimeO(3^n)Every stone can branch into up to three jump sizes and the same (stone, jump) pairs are explored repeatedly.
SpaceO(n)The recursion depth is at most the number of stones.

Recursively explore every legal jump. From stone i with last jump k, look at the following stones whose distance is k - 1, k or k + 1 and recurse into each of them. Succeed as soon as one path reaches the last stone.

  1. Call dfs(0, 0): on stone 0, previous jump 0 (so the only legal first jump is 1).
  2. If i is the last stone, return true.
  3. For each later stone j, let gap = stones[j] - stones[i]. Stop once gap > k + 1; if gap >= k - 1, recurse into dfs(j, gap).
  4. Return false if no branch succeeds.
class Solution {
    public boolean canCross(int[] stones) {
        return dfs(stones, 0, 0);
    }

    private boolean dfs(int[] stones, int i, int k) {
        if (i == stones.length - 1) return true;
        for (int j = i + 1; j < stones.length; j++) {
            long gap = (long) stones[j] - stones[i];
            if (gap > k + 1) break;
            if (gap >= k - 1 && dfs(stones, j, (int) gap)) return true;
        }
        return false;
    }
}

2Optimal (jump sizes per stone)

TimeO(n²)A stone can be landed on with at most n different jump sizes, and each size does three O(1) hash lookups.
SpaceO(n²)The sets together hold up to O(n²) (stone, jump size) pairs.

Map every stone position to the set of jump sizes that can land on it. Process stones from left to right: for every size k that reached stone s, the frog can continue with k - 1, k or k + 1, so add that size to the set of the stone at s + size if such a stone exists. The last stone is reachable exactly when its set is non-empty.

  1. Create an empty set for every stone; put size 0 into the set of stone 0 (a virtual previous jump).
  2. For each stone s in increasing order and each size k in its set, try step in k - 1, k, k + 1 with step > 0.
  3. If a stone exists at s + step (use 64-bit arithmetic), add step to its set.
  4. Return whether the last stone's set is non-empty.
class Solution {
    public boolean canCross(int[] stones) {
        Map<Long, Set<Integer>> sizes = new HashMap<>();
        for (int s : stones) sizes.put((long) s, new HashSet<>());
        sizes.get(0L).add(0);
        for (int s : stones) {
            for (int k : sizes.get((long) s)) {
                for (int step = k - 1; step <= k + 1; step++) {
                    if (step <= 0) continue;
                    Set<Integer> next = sizes.get((long) s + step);
                    if (next != null) next.add(step);
                }
            }
        }
        return !sizes.get((long) stones[stones.length - 1]).isEmpty();
    }
}

Edge cases to test

  • Only two stones: the answer is true exactly when the second stone is at position 1
  • Consecutive positions 0, 1, 2, … (always reachable with jumps of 1)
  • A gap that grows faster than the frog can speed up
  • Several different jump sizes landing on the same stone; only some of them lead onward
  • Very large positions near 2^31 - 1, where position + jump overflows a 32-bit int

Hints

Hint 1

The frog's situation is fully described by two things: which stone it is on and how long its last jump was.

Hint 2

Try all three next jump sizes recursively. Many (stone, last jump) pairs are reached again and again.

Hint 3

Instead of recursing, walk the stones left to right and keep, for each stone, the set of jump sizes that can land on it. Push each of them forward with sizes k - 1, k and k + 1.

FAQ

What is the best time complexity for Frog Jump?

Optimal (jump sizes per stone) runs in O(n²) time and O(n²) extra space. A stone can be landed on with at most n different jump sizes, and each size does three O(1) hash lookups.

Which pattern does Frog Jump use?

It is a dynamic programming problem that uses the 1d dp pattern. Other problems with the same pattern: Fibonacci Number, Climbing Stairs, Min Cost Climbing Stairs (2 jumps).

Is there a brute force solution for Frog Jump?

Yes. Brute force (try every jump sequence) takes O(3^n) time and O(n) space. Recursively explore every legal jump.

Which edge cases should I test for Frog Jump?

Only two stones: the answer is true exactly when the second stone is at position 1; Consecutive positions 0, 1, 2, … (always reachable with jumps of 1); A gap that grows faster than the frog can speed up; Several different jump sizes landing on the same stone; only some of them lead onward; Very large positions near 2^31 - 1, where position + jump overflows a 32-bit int.