Skip to main content
Talentd

Jump Game III - Solution & Explanation

MediumArrayDepth-First SearchBreadth-First Search18 min readAsked at: Amazon, Microsoft, Tanium
Practice this problem

Problem Statement

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 * 104
  • 0 <= arr[i] < arr.length
  • 0 <= 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.

In this C implementation, a helper function canReachHelper is defined to handle recursion and keep track of visited indices using an array. If we reach a position with value 0, we return true. Otherwise, the recursion explores possible jumps both forward and backward. Memory for the visited array is allocated and freed appropriately to avoid memory leaks.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the array, because every index is visited at most once.
Space Complexity: O(n) due to the recursion stack and the visited array.

Try this approach in the editor →

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.

Here's how the C solution works: A queue is dynamically created and used to explore all potential positions, marking indices as visited in a dedicated boolean array. By processing each queue element, we're checking both forward and backward jumps. This approach terminates when an index with a zero value is found or when the queue is empty.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), as all reachable indices are visited.
Space Complexity: O(n), given the storage requirements for the queue and the visited array.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Depth-First Search (DFS)

Time Complexity: O(n), where n is the length of the array, because every index is visited at most once.
Space Complexity: O(n) due to the recursion stack and the visited array.

Breadth-First Search (BFS)

Time Complexity: O(n), as all reachable indices are visited.
Space Complexity: O(n), given the storage requirements for the queue and the visited array.

BFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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

Video Solution

Jump Game III | Live Coding with Explanation | Leetcode - 1306 • Algorithms Made Easy • 8,315 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Jump Game III with our built-in code editor and test cases.

Practice on FleetCode
Previous

Jump Game

Next

Jump Game II