Scale Engineer

Jump Game III

Med
#1216Time: O(N), where N is the length of the array. Each index is visited at most once.Space: O(N). This is composed of O(N) for the `visited` array and O(N) for the recursion call stack in the worst-case scenario (e.g., a long chain of jumps).3 companies
Algorithms
Depth-First SearchBreadth-First Search
Data structures
Array
Companies
SnapPinterestTanium

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach models the problem as a graph traversal. The array indices are the nodes, and the possible jumps define the edges. We use Depth-First Search (DFS) to explore all reachable indices from the start index. To prevent getting stuck in infinite loops (cycles), we use an auxiliary boolean array visited to keep track of the indices we have already explored.

Algorithm

  1. Initialize a boolean array visited of size arr.length to all false.
  2. Define a recursive function dfs(index): a. If index is out of bounds or visited[index] is true, return false. b. If arr[index] == 0, return true. c. Mark visited[index] = true. d. Explore right: foundRight = dfs(index + arr[index]). e. Explore left: foundLeft = dfs(index - arr[index]). f. Return foundRight || foundLeft.
  3. Call dfs(start) and return its result.

Walkthrough

The algorithm starts a recursive traversal from the start index. A visited array of the same size as the input array arr is initialized to all false. The recursive function canReachRecursive(currentIndex, arr, visited) works as follows:

  1. Base Case (Out of Bounds): If currentIndex is less than 0 or greater than or equal to arr.length, it's an invalid jump. Return false.
  2. Base Case (Already Visited): If visited[currentIndex] is true, we have already been at this index. To avoid a cycle, we return false.
  3. Base Case (Target Found): If arr[currentIndex] is 0, we have reached a target index. Return true.
  4. Mark as Visited: Set visited[currentIndex] = true to mark that we are currently exploring from this index.
  5. Recursive Step: Explore the two possible jumps:
    • Jump forward: canReachRecursive(currentIndex + arr[currentIndex], arr, visited)
    • Jump backward: canReachRecursive(currentIndex - arr[currentIndex], arr, visited)
  6. If either of the recursive calls returns true, it means a path to a 0 exists, so we return true. Otherwise, return false. The main function initializes the visited array and calls the recursive function with the start index.
class Solution {    public boolean canReach(int[] arr, int start) {        boolean[] visited = new boolean[arr.length];        return canReachRecursive(arr, start, visited);    }     private boolean canReachRecursive(int[] arr, int index, boolean[] visited) {        // Base case: out of bounds        if (index < 0 || index >= arr.length) {            return false;        }        // Base case: already visited        if (visited[index]) {            return false;        }        // Base case: target found        if (arr[index] == 0) {            return true;        }         // Mark as visited        visited[index] = true;         // Recursive step        boolean found = canReachRecursive(arr, index + arr[index], visited) ||                        canReachRecursive(arr, index - arr[index], visited);         return found;    }}

Complexity

Time

O(N), where N is the length of the array. Each index is visited at most once.

Space

O(N). This is composed of O(N) for the `visited` array and O(N) for the recursion call stack in the worst-case scenario (e.g., a long chain of jumps).

Trade-offs

Pros

  • Conceptually simple and directly translates the problem's recursive nature.

  • Correctly handles cycles.

Cons

  • Can lead to a StackOverflowError for very deep recursion paths (long chains of jumps).

  • Uses extra space for both the visited array and the recursion stack.

Solutions

class Solution {public  boolean canReach(int[] arr, int start) {    Deque<Integer> q = new ArrayDeque<>();    q.offer(start);    while (!q.isEmpty()) {      int i = q.poll();      if (arr[i] == 0) {        return true;      }      int x = arr[i];      arr[i] = -1;      for (int j : List.of(i + x, i - x)) {        if (j >= 0 && j < arr.length && arr[j] >= 0) {          q.offer(j);        }      }    }    return false;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem