Jump Game III solution and explanation
9 more videos on this problem
Jump Game III | Live Coding with Explanation | Leetcode - 1306Algorithms Made Easy · 6:35 · 8K views
Jump Game 3 (LeetCode 1306) | Simplified solution with diagrams | Level Order Traversal | BFSNikhil Lohia · 20:57 · 5K views
Jump Game III | Leetcode 1306 | Depth First Search | ArraysNideesh Terapalli · 5:20 · 3K views
Jump Game iii | LeetCode 1306 | C++Knowledge Center · 10:44 · 2K views
Jump Game III | Leet code 1306 | Theory explained + Python codeSai Anish Malla · 9:27 · 1K views
1306. Jump Game III [LeetCode Time with AlgoTips]AlgoTips · 8:35 · 599 views
1306. Jump Game III | Leetcode Daily - PythonLeetcode Daily · 6:15 · 284 views
Jump Game III | Recursion | Explanation on WhiteBoard | Leetcode # 1306Binod Suman Academy · 15:57 · 268 views
Daily Leetcode #618: Dec 09, 2021 - 1306. Jump Game IIIProgramming Live with Larry · 8:26 · 192 views
Jump Game III | LeetCode 1306 - Pythonimpoldev · 4:11 · 155 views
The problem
Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach any index with value 0.
Notice that you can not jump outside of the array at any time.
Example 1:
Input: arr = [4,2,3,0,3,1,2], start = 5 Output: true Explanation: All possible ways to reach at index 3 with value 0 are: index 5 -> index 4 -> index 1 -> index 3 index 5 -> index 6 -> index 4 -> index 1 -> index 3
Example 2:
Input: arr = [4,2,3,0,3,1,2], start = 0 Output: true Explanation: One possible way to reach at index 3 with value 0 is: index 0 -> index 4 -> index 1 -> index 3
Example 3:
Input: arr = [3,0,2,1,2], start = 2 Output: false Explanation: There is no way to reach at index 1 with value 0.
Constraints:
1 <= arr.length <= 5 * 1040 <= arr[i] < arr.length0 <= start < arr.length
Approach overview
Problem Overview: You are given an array arr and a starting index start. From index i, you can jump to i + arr[i] or i - arr[i]. The goal is to determine whether you can reach any index whose value is 0. The array behaves like a graph where each index is a node and jumps create edges.
The core challenge is avoiding infinite loops. Since jumps can revisit the same index repeatedly, the solution must track visited positions while exploring reachable indices.
Approach 1: Depth-First Search (DFS) (Time: O(n), Space: O(n))
Treat the array as a graph and explore it using recursion or an explicit stack. Start at the given index and recursively attempt both possible jumps: i + arr[i] and i - arr[i]. Maintain a visited set (or mark elements in-place) to prevent revisiting indices, which would otherwise create cycles. Each index is processed at most once, so the traversal runs in linear time. DFS works well because you only need to check reachability, not the shortest path. If any recursive path reaches an index with value 0, return true immediately.
This approach highlights the connection between arrays and graph traversal problems. You systematically explore neighbors while enforcing boundary checks (0 ≤ index < n) and skipping already visited nodes.
Approach 2: Breadth-First Search (BFS) (Time: O(n), Space: O(n))
BFS explores indices level by level using a queue. Start by pushing the start index into the queue. At each step, pop an index and check if its value is 0. If not, compute the two reachable indices and push valid, unvisited ones into the queue. Mark them as visited immediately to avoid duplicates.
BFS guarantees each index enters the queue at most once, giving the same O(n) time complexity. The space complexity is also O(n) due to the queue and visited tracking. This approach is often easier to reason about iteratively and mirrors standard graph traversal patterns used in many interview problems.
Both DFS and BFS rely on the same insight: the array forms an implicit graph where edges represent legal jumps. Efficient traversal requires marking visited nodes to avoid cycles.
Recommended for interviews: Either DFS or BFS is acceptable since both achieve optimal O(n) time complexity. DFS is slightly shorter to implement recursively, while BFS demonstrates explicit graph traversal skills. Interviewers mainly look for two things: recognizing the problem as a graph reachability problem and preventing infinite loops with a visited structure. Practicing both approaches strengthens understanding of Depth-First Search, Breadth-First Search, and graph-style traversal on an array.
Approach 1: Depth-First Search (DFS)
This approach employs DFS for exploring each possible path starting from the given start index. You recursively explore both forward and backward jumps, marking indices as visited to avoid cycles. If you reach an index with a value of 0, return true. If all paths are exhausted without finding a zero, return false.
class Solution:
def canReach(self, arr: list[int], start: int) -> bool:
def dfs(pos: int) -> bool:
if pos < 0 or pos >= len(arr) or arr[pos] < 0:
return False
if arr[pos] == 0:
return True
jump = arr[pos]
arr[pos] = -arr[pos] # Mark as visited
result = dfs(pos + jump) or dfs(pos - jump)
arr[pos] = -arr[pos] # Reset
return result
return dfs(start)import java.util.*;
public class Solution {
public boolean canReach(int[] arr, int start) {
return dfs(arr, start);
}
private boolean dfs(int[] arr, int pos) {
if (pos < 0 || pos >= arr.length || arr[pos] < 0)
return false;
if (arr[pos] == 0)
return true;
int jump = arr[pos];
arr[pos] = -arr[pos]; // Mark visited
boolean result = dfs(arr, pos + jump) || dfs(arr, pos - jump);
arr[pos] = -arr[pos]; // Reset
return result;
}
}#include <vector>
#include <iostream>
class Solution {
public:
bool canReach(std::vector<int>& arr, int start) {
return dfs(arr, start);
}
private:
bool dfs(std::vector<int>& arr, int pos) {
if (pos < 0 || pos >= arr.size() || arr[pos] < 0)
return false;
if (arr[pos] == 0)
return true;
int jump = arr[pos];
arr[pos] = -arr[pos]; // Mark as visited
bool result = dfs(arr, pos + jump) || dfs(arr, pos - jump);
arr[pos] = -arr[pos]; // Reset the marked value
return result;
}
};var canReach = function(arr, start) {
const dfs = (arr, pos) => {
if (pos < 0 || pos >= arr.length || arr[pos] < 0)
return false;
if (arr[pos] === 0)
return true;
const jump = arr[pos];
arr[pos] = -arr[pos]; // Mark visited
const result = dfs(arr, pos + jump) || dfs(arr, pos - jump);
arr[pos] = -arr[pos]; // Reset
return result;
};
return dfs(arr, start);
};#include <stdbool.h>
#include <stdlib.h>
bool canReachHelper(int* arr, int arrSize, int start, bool* visited) {
if (start < 0 || start >= arrSize || visited[start])
return false;
if (arr[start] == 0)
return true;
visited[start] = true;
return canReachHelper(arr, arrSize, start + arr[start], visited) ||
canReachHelper(arr, arrSize, start - arr[start], visited);
}
bool canReach(int* arr, int arrSize, int start) {
bool* visited = (bool*)calloc(arrSize, sizeof(bool));
bool result = canReachHelper(arr, arrSize, start, visited);
free(visited);
return result;
}public class Solution {
public bool CanReach(int[] arr, int start) {
return Dfs(arr, start);
}
private bool Dfs(int[] arr, int pos) {
if (pos < 0 || pos >= arr.Length || arr[pos] < 0)
return false;
if (arr[pos] == 0)
return true;
int jump = arr[pos];
arr[pos] = -arr[pos]; // Mark visited
bool result = Dfs(arr, pos + jump) || Dfs(arr, pos - jump);
arr[pos] = -arr[pos]; // Reset
return result;
}
}The Python solution also uses a DFS approach similar to other implementations. Instead of a separate visited list, it marks visited indices directly in the array by negating the values. The recursive function dfs checks bounds, performs the value check, and makes recursive calls to explore each possible jump path.
Time Complexity: O(n). Each index is visited at most once.
Space Complexity: O(n) for the recursion stack.
Approach 2: Breadth-First Search (BFS)
This approach adopts a BFS strategy to explore all reachable indices from the starting point iteratively. Using a queue, enqueue all possible jump indices from a given position if they haven't been visited yet. Pop indices from the queue, and for each pop, check whether the position contains a zero, marking indices visited as you go.
from collections import deque
class Solution:
def canReach(self, arr: list[int], start: int) -> bool:
queue = deque([start])
visited = [False] * len(arr)
visited[start] = True
while queue:
curr = queue.popleft()
if arr[curr] == 0:
return True
for next_pos in (curr + arr[curr], curr - arr[curr]):
if 0 <= next_pos < len(arr) and not visited[next_pos]:
visited[next_pos] = True
queue.append(next_pos)
return Falseimport java.util.*;
public class Solution {
public boolean canReach(int[] arr, int start) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[arr.length];
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int curr = queue.poll();
if (arr[curr] == 0)
return true;
int nextPos = curr + arr[curr];
int prevPos = curr - arr[curr];
if (nextPos < arr.length && !visited[nextPos]) {
visited[nextPos] = true;
queue.add(nextPos);
}
if (prevPos >= 0 && !visited[prevPos]) {
visited[prevPos] = true;
queue.add(prevPos);
}
}
return false;
}
}#include <vector>
#include <queue>
class Solution {
public:
bool canReach(std::vector<int>& arr, int start) {
std::queue<int> q;
std::vector<bool> visited(arr.size(), false);
q.push(start);
visited[start] = true;
while (!q.empty()) {
int curr = q.front();
q.pop();
if (arr[curr] == 0)
return true;
int nextPos = curr + arr[curr];
int prevPos = curr - arr[curr];
if (nextPos < arr.size() && !visited[nextPos]) {
visited[nextPos] = true;
q.push(nextPos);
}
if (prevPos >= 0 && !visited[prevPos]) {
visited[prevPos] = true;
q.push(prevPos);
}
}
return false;
}
};var canReach = function(arr, start) {
const queue = [start];
const visited = new Array(arr.length).fill(false);
visited[start] = true;
while (queue.length > 0) {
const curr = queue.shift();
if (arr[curr] === 0)
return true;
for (const nextPos of [curr + arr[curr], curr - arr[curr]]) {
if (nextPos >= 0 && nextPos < arr.length && !visited[nextPos]) {
visited[nextPos] = true;
queue.push(nextPos);
}
}
}
return false;
};#include <stdbool.h>
#include <stdlib.h>
struct Queue {
int *data;
int front;
int rear;
int capacity;
};
struct Queue* createQueue(int capacity) {
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->capacity = capacity;
queue->front = queue->rear = 0;
queue->data = (int*)malloc(queue->capacity * sizeof(int));
return queue;
}
void enqueue(struct Queue* queue, int item) {
queue->data[queue->rear++] = item;
}
int dequeue(struct Queue* queue) {
return queue->data[queue->front++];
}
bool isQueueEmpty(struct Queue* queue) {
return queue->front == queue->rear;
}
void freeQueue(struct Queue* queue) {
free(queue->data);
free(queue);
}
bool canReach(int* arr, int arrSize, int start) {
struct Queue* queue = createQueue(arrSize);
bool* visited = (bool*)calloc(arrSize, sizeof(bool));
enqueue(queue, start);
visited[start] = true;
while (!isQueueEmpty(queue)) {
int curr = dequeue(queue);
if (arr[curr] == 0) {
freeQueue(queue);
free(visited);
return true;
}
int nextPos = curr + arr[curr];
int prevPos = curr - arr[curr];
if (nextPos < arrSize && !visited[nextPos]) {
visited[nextPos] = true;
enqueue(queue, nextPos);
}
if (prevPos >= 0 && !visited[prevPos]) {
visited[prevPos] = true;
enqueue(queue, prevPos);
}
}
freeQueue(queue);
free(visited);
return false;
}using System;
using System.Collections.Generic;
public class Solution {
public bool CanReach(int[] arr, int start) {
Queue<int> queue = new Queue<int>();
bool[] visited = new bool[arr.Length];
queue.Enqueue(start);
visited[start] = true;
while (queue.Count > 0) {
int curr = queue.Dequeue();
if (arr[curr] == 0)
return true;
int nextPos = curr + arr[curr];
int prevPos = curr - arr[curr];
if (nextPos < arr.Length && !visited[nextPos]) {
visited[nextPos] = true;
queue.Enqueue(nextPos);
}
if (prevPos >= 0 && !visited[prevPos]) {
visited[prevPos] = true;
queue.Enqueue(prevPos);
}
}
return false;
}
}The Python solution uses a deque to manage the exploration queue, marking indices as visited in an auxiliary boolean list. By iterating over the two possible jumps from each current index, the solution entirely embodies a typical BFS workflow.
Time Complexity: O(n), because it processes each index once.
Space Complexity: O(n) due to the queue and the visited array.
Approach 3: BFS
We can use BFS to determine whether we can reach the index with a value of 0.
Define a queue q to store the currently reachable indices. Initially, enqueue the start index.
When the queue is not empty, take out the front index i of the queue. If arr[i] = 0, return true. Otherwise, mark the index i as visited. If i + arr[i] and i - arr[i] are within the array range and have not been visited, enqueue them and continue searching.
Finally, if the queue is empty, it means that we cannot reach the index with a value of 0, so return false.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array.
function canReach(arr: number[], start: number): boolean {
const q = [start];
for (const i of q) {
if (arr[i] === 0) {
return true;
}
if (arr[i] === -1 || arr[i] === undefined) {
continue;
}
q.push(i + arr[i], i - arr[i]);
arr[i] = -1;
}
return false;
}func canReach(arr []int, start int) bool {
q := []int{start}
for len(q) > 0 {
i := q[0]
q = q[1:]
if arr[i] == 0 {
return true
}
x := arr[i]
arr[i] = -1
for _, j := range []int{i + x, i - x} {
if j >= 0 && j < len(arr) && arr[j] >= 0 {
q = append(q, j)
}
}
}
return false
}Complexity comparison
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) | Time Complexity: O(n). Each index is visited at most once. |
| Breadth-First Search (BFS) | Time Complexity: O(n), because it processes each index once. |
| BFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) | O(n) | O(n) | When recursive traversal is preferred and you want a concise reachability check |
| Breadth-First Search (BFS) | O(n) | O(n) | When you prefer iterative traversal using a queue or want clearer control over exploration order |
Frequently asked questions
Is Jump Game III easy or hard?
Jump Game III is considered a medium-level problem. The logic becomes straightforward once you recognize the array as an implicit graph and apply BFS or DFS while preventing cycles with a visited structure.
Jump Game III Python/Java solution
Python and Java implementations typically use either DFS recursion or a BFS queue. Both approaches maintain a visited array or modify the input array to mark visited indices. The algorithm runs in O(n) time and O(n) space regardless of language.
How to solve Jump Game III in O(n)?
Model the array as a graph and perform DFS or BFS starting from the given index. For every visited index, attempt jumps to i + arr[i] and i - arr[i], ensuring the index stays within bounds and has not been visited before. Stop when you reach a value of 0. Each index is explored once, leading to O(n) time and O(n) space.
What is the best approach for Jump Game III?
Depth-First Search (DFS) or Breadth-First Search (BFS) are the best approaches. Both treat the array as a graph where each index connects to i + arr[i] and i - arr[i]. By tracking visited indices, you avoid cycles and ensure each index is processed once, giving O(n) time complexity.
Is Jump Game III asked at Google/Amazon/Meta?
Jump Game III is a common medium-level graph traversal problem and has appeared in interview preparation lists for companies like Amazon and Google. It tests understanding of graph reachability, cycle prevention, and BFS/DFS traversal patterns.
What data structure is used in Jump Game III?
The solution primarily uses graph traversal data structures. DFS implementations rely on recursion or a stack, while BFS uses a queue. A visited set or boolean array is also required to track indices that have already been explored.
What is the time complexity of Jump Game III?
The optimal time complexity is O(n) because each index in the array is visited at most once. Both DFS and BFS mark visited indices to prevent revisiting nodes, ensuring the traversal does not exceed linear time.