Frog Jump
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 <= 20000 <= stones[i] <= 2^31 - 1stones[0] == 0stonesis 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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)
O(3^n)Every stone can branch into up to three jump sizes and the same (stone, jump) pairs are explored repeatedly.O(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.
- Call
dfs(0, 0): on stone 0, previous jump 0 (so the only legal first jump is 1). - If
iis the last stone, return true. - For each later stone
j, letgap = stones[j] - stones[i]. Stop oncegap > k + 1; ifgap >= k - 1, recurse intodfs(j, gap). - 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;
}
}class Solution:
def canCross(self, stones: List[int]) -> bool:
n = len(stones)
def dfs(i: int, k: int) -> bool:
if i == n - 1:
return True
for j in range(i + 1, n):
gap = stones[j] - stones[i]
if gap > k + 1:
break
if gap >= k - 1 and dfs(j, gap):
return True
return False
return dfs(0, 0)class Solution {
public:
bool canCross(vector<int>& stones) {
return dfs(stones, 0, 0);
}
private:
bool dfs(vector<int>& stones, int i, long long k) {
int n = stones.size();
if (i == n - 1) return true;
for (int j = i + 1; j < n; j++) {
long long gap = (long long)stones[j] - stones[i];
if (gap > k + 1) break;
if (gap >= k - 1 && dfs(stones, j, gap)) return true;
}
return false;
}
};function canCross(stones) {
const n = stones.length;
const dfs = (i, k) => {
if (i === n - 1) return true;
for (let j = i + 1; j < n; j++) {
const gap = stones[j] - stones[i];
if (gap > k + 1) break;
if (gap >= k - 1 && dfs(j, gap)) return true;
}
return false;
};
return dfs(0, 0);
}2Optimal (jump sizes per stone)
O(n²)A stone can be landed on with at most n different jump sizes, and each size does three O(1) hash lookups.O(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.
- Create an empty set for every stone; put size 0 into the set of stone 0 (a virtual previous jump).
- For each stone
sin increasing order and each sizekin its set, trystepink - 1, k, k + 1withstep > 0. - If a stone exists at
s + step(use 64-bit arithmetic), addstepto its set. - 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();
}
}class Solution:
def canCross(self, stones: List[int]) -> bool:
sizes = {s: set() for s in stones}
sizes[0].add(0)
for s in stones:
for k in sizes[s]:
for step in (k - 1, k, k + 1):
if step > 0 and s + step in sizes:
sizes[s + step].add(step)
return len(sizes[stones[-1]]) > 0class Solution {
public:
bool canCross(vector<int>& stones) {
unordered_map<long long, unordered_set<int>> sizes;
for (int s : stones) sizes[s];
sizes[0].insert(0);
for (int s : stones) {
for (int k : sizes[s]) {
for (int step = k - 1; step <= k + 1; step++) {
if (step <= 0) continue;
auto it = sizes.find((long long)s + step);
if (it != sizes.end()) it->second.insert(step);
}
}
}
return !sizes[stones.back()].empty();
}
};function canCross(stones) {
const sizes = new Map();
for (const s of stones) sizes.set(s, new Set());
sizes.get(0).add(0);
for (const s of stones) {
for (const k of sizes.get(s)) {
for (let step = k - 1; step <= k + 1; step++) {
if (step <= 0) continue;
const next = sizes.get(s + step);
if (next !== undefined) next.add(step);
}
}
}
return sizes.get(stones[stones.length - 1]).size > 0;
}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.