Jump Game III — Solution in Python, Java & C++
Jump Game III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Jump Game III is a medium coding problem on arrays, depth-first search and breadth-first search, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Depth-First Search, Breadth-First Search
- Asked at: Amazon, Google, Meta
- 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
Given an array of non-negative integers arr and a starting index start, you may jump from index i to i + arr[i] or i - arr[i], provided you stay inside the array.
Return true if you can reach any index holding the value 0.
Example 1
Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Example 2
Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true
Example 3
Input: arr = [3,0,2,1,2], start = 2
Output: false
Constraints
1 <= arr.length <= 400 <= arr[i] < arr.length0 <= start < arr.length
Hints for Jump Game III
Hint 1
Treat the indices as graph nodes with two outgoing edges each.
Hint 2
Run a DFS or BFS from
start, marking indices as you visit them.Hint 3
The marking is what keeps you out of an infinite loop when jumps bounce back and forth.
How to solve Jump Game III
Indices are nodes with two outgoing edges (i ± arr[i]); DFS/BFS from start with a visited set, returning true on any index holding 0.
Approach
- Push
start, marking it. - Pop; if
arr[index] == 0returntrue; push unseen in-range neighbours. - Return
false.
Why it works
Reachability in the implicit graph is exactly the question, and the visited set prevents the bounce-back loop.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Without marking,
[1, 1]-style inputs loop forever.
Reference solution
Python
def canReach(arr, start: int) -> bool:
n = len(arr)
seen = [False] * n
seen[start] = True
stack = [start]
while stack:
index = stack.pop()
if arr[index] == 0:
return True
for nxt in (index + arr[index], index - arr[index]):
if 0 <= nxt < n and not seen[nxt]:
seen[nxt] = True
stack.append(nxt)
return FalseJava
public static boolean canReach(int[] arr, int start) {
int n = arr.length;
boolean[] seen = new boolean[n];
seen[start] = true;
Deque<Integer> stack = new ArrayDeque<>();
stack.push(start);
while (!stack.isEmpty()) {
int index = stack.pop();
if (arr[index] == 0) return true;
int forward = index + arr[index];
int backward = index - arr[index];
if (forward < n && !seen[forward]) {
seen[forward] = true;
stack.push(forward);
}
if (backward >= 0 && !seen[backward]) {
seen[backward] = true;
stack.push(backward);
}
}
return false;
}C++
bool canReach(vector<int>& arr, int start) {
int n = (int) arr.size();
vector<bool> seen(n, false);
seen[start] = true;
vector<int> stack;
stack.push_back(start);
while (!stack.empty()) {
int index = stack.back();
stack.pop_back();
if (arr[index] == 0) return true;
int forward = index + arr[index];
int backward = index - arr[index];
if (forward < n && !seen[forward]) {
seen[forward] = true;
stack.push_back(forward);
}
if (backward >= 0 && !seen[backward]) {
seen[backward] = true;
stack.push_back(backward);
}
}
return false;
}JavaScript
var canReach = function(arr, start) {
const n = arr.length;
const seen = [];
for (let i = 0; i < n; i++) seen.push(false);
seen[start] = true;
const stack = [start];
while (stack.length > 0) {
const index = stack.pop();
if (arr[index] === 0) return true;
const forward = index + arr[index];
const backward = index - arr[index];
if (forward < n && !seen[forward]) {
seen[forward] = true;
stack.push(forward);
}
if (backward >= 0 && !seen[backward]) {
seen[backward] = true;
stack.push(backward);
}
}
return false;
};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 · Depth-First Search (DFS)