Frog Jump — Solution in Python, Java & C++
Frog Jump solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.
Frog Jump is a hard coding problem on arrays, hash table and dynamic programming, asked in Amazon, Google, Microsoft and Snapchat interviews.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Dynamic Programming
- Asked at: Amazon, Google, Microsoft, Snapchat
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A frog crosses a river on stones at the positions listed in stones (strictly increasing, starting at 0). It begins on the first stone and its first jump must be 1 unit.
If the last jump was k units, the next must be k - 1, k or k + 1 units, always forwards. Return whether the frog can reach the last stone.
Example 1
Input: stones = [0,1,3,5,6,8,12,17]
Output: true
Explanation: Jumps of 1, 2, 2, 3, 4 and 5 reach the end.
Example 2
Input: stones = [0,1,2,3,4,8,9,11]
Output: false
Explanation: The gap from 4 to 8 is too wide for the jump built up so far.
Example 3
Input: stones = [0,1]
Output: true
Constraints
2 <= stones.length <= 10000 <= stones[i] <= 1000000000stones[0] == 0stones is sorted strictly increasing.
Hints for Frog Jump
Hint 1
The state is the pair (stone, size of the jump that landed there) — position alone is not enough.
Hint 2
From a state, three jump sizes are possible, and each must land exactly on another stone.
Hint 3
Keep a set of reachable jump sizes per stone and push forwards.
How to solve Frog Jump
Forward reachability over states (stone, lastJump). From each reachable state, try the three legal jump sizes and mark the landing stone reachable with that size.
Approach
- Map each stone position to its index for constant-time landing checks.
- Seed stone 0 with jump size 0, so the only legal first move is size 1.
- For each stone in order, for each recorded jump size
k, tryk-1,kandk+1, skipping non-positive sizes. - The frog can cross when the last stone has any recorded jump size.
Why it works
The next legal jumps depend only on the size of the jump just made, so (stone, lastJump) is a sufficient state. Processing stones left to right is safe because every jump moves strictly forwards, so a state is finalised before it is used. The jump size never exceeds the number of stones, which bounds the state space.
Complexity
- Time —
O(n²) - Space —
O(n²)
Pitfalls
- Tracking only the stone, not the jump size, loses the information the rules depend on.
- A jump of size 0 or less is illegal and must be skipped — seeding stone 0 with 0 is what forces the first jump to be 1.
- The landing must be exactly on a stone; there is no partial progress.
Reference solution
Python
from typing import List
def canCross(stones: List[int]) -> bool:
n = len(stones)
pos = {s: i for i, s in enumerate(stones)}
dp = [set() for _ in range(n)]
dp[0].add(0)
for i in range(n):
for k in list(dp[i]):
for step in (k - 1, k, k + 1):
if step <= 0:
continue
nxt = stones[i] + step
if nxt in pos:
dp[pos[nxt]].add(step)
return len(dp[n - 1]) > 0Java
public static boolean canCross(int[] stones) {
int n = stones.length;
Map<Integer, Integer> pos = new HashMap<>();
for (int i = 0; i < n; i++) pos.put(stones[i], i);
List<Set<Integer>> dp = new ArrayList<>();
for (int i = 0; i < n; i++) dp.add(new HashSet<>());
dp.get(0).add(0);
for (int i = 0; i < n; i++) {
for (int k : new ArrayList<>(dp.get(i))) {
for (int step = k - 1; step <= k + 1; step++) {
if (step <= 0) continue;
Integer idx = pos.get(stones[i] + step);
if (idx != null) dp.get(idx).add(step);
}
}
}
return !dp.get(n - 1).isEmpty();
}C++
bool canCross(vector<int>& stones) {
int n = (int) stones.size();
unordered_map<int, int> pos;
for (int i = 0; i < n; i++) pos[stones[i]] = i;
vector<set<int>> dp(n);
dp[0].insert(0);
for (int i = 0; i < n; i++) {
vector<int> ks(dp[i].begin(), dp[i].end());
for (int k : ks) {
for (int step = k - 1; step <= k + 1; step++) {
if (step <= 0) continue;
auto it = pos.find(stones[i] + step);
if (it != pos.end()) dp[it->second].insert(step);
}
}
}
return !dp[n - 1].empty();
}JavaScript
var canCross = function(stones) {
var n = stones.length;
var pos = {}, i;
for (i = 0; i < n; i++) pos[stones[i]] = i;
var dp = [];
for (i = 0; i < n; i++) dp.push({});
dp[0][0] = true;
for (i = 0; i < n; i++) {
var keys = Object.keys(dp[i]);
for (var t = 0; t < keys.length; t++) {
var k = Number(keys[t]);
var steps = [k - 1, k, k + 1];
for (var q = 0; q < 3; q++) {
var step = steps[q];
if (step <= 0) continue;
var nxt = stones[i] + step;
if (pos[nxt] !== undefined) dp[pos[nxt]][step] = true;
}
}
}
return Object.keys(dp[n - 1]).length > 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets