Jump Game III

Medium
468.

Jump Game III

Jump Game III is a medium coding problem on arrays, depth-first search and breadth-first search, asked in Amazon, Google and Meta interviews.

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 <= 40
  • 0 <= arr[i] < arr.length
  • 0 <= start < arr.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} start
 * @return {boolean}
 */
var canReach = function(arr, start) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Jump Game III

  1. Hint 1

    Treat the indices as graph nodes with two outgoing edges each.

  2. Hint 2

    Run a DFS or BFS from start, marking indices as you visit them.

  3. 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

  1. Push start, marking it.
  2. Pop; if arr[index] == 0 return true; push unseen in-range neighbours.
  3. 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 False

Java

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)