Jump Game III

LeetCode 1428 | Difficulty: Medium

Medium

Problem Description

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 * 10^4`

- `0 <= arr[i] < arr.length`

- `0 <= start < arr.length`

Topics: Array, Depth-First Search, Breadth-First Search

---

Approach

BFS (Graph/Matrix)

Use a queue to explore nodes level by level. Start from source node(s), visit all neighbors before moving to the next level. BFS naturally finds shortest paths in unweighted graphs.

When to use

Shortest path in unweighted graph, level-order processing, spreading/flood fill.

---

Solutions

Solution 1: C# (Best: 227 ms)

Metric	Value
Runtime	227 ms
Memory	47.1 MB
Date	2022-01-28

Solution

public class Solution {
    public bool CanReach(int[] arr, int start) {
    int n = arr.Length;
    if(arr[start] == 0) return true;
    Queue<int> q = new Queue<int>();
    q.Enqueue(start);
    while(q.Count != 0)
    {
        var popped = q.Dequeue();
        
        int left = popped - arr[popped];
        int right = popped + arr[popped];
        
        if(left >= 0 && arr[left] >= 0)
        {
            if(arr[left] == 0) return true;
            q.Enqueue(left);
        }
        if (right < n && arr[right] >=0)
        {
            if(arr[right] == 0) return true;
            q.Enqueue(right);
        }
        arr[popped] *= -1;
    }
    return false;
    }
}

📜 2 more C# submission(s)

Submission (2022-01-28) — 1379 ms, 47 MB

public class Solution {
    public bool CanReach(int[] arr, int start) {
        List<int> seen = new List<int>();
    int n = arr.Length;
    if(arr[start] == 0) return true;
    Queue<int> q = new Queue<int>();
    q.Enqueue(start);
    seen.Add(start);
    while(q.Count != 0)
    {
        var popped = q.Dequeue();

        int left = popped - arr[popped];
        int right = popped + arr[popped];
        
        if(left >= 0 && left< n && !seen.Contains(left))
        {
            if(arr[left] == 0) return true;
            seen.Add(left);
            q.Enqueue(left);
        }
        if (right >= 0 && right < n && !seen.Contains(right))
        {
            if(arr[right] == 0) return true;
            seen.Add(right);
            q.Enqueue(right);
        }
    }
    return false;
    }
}

Submission (2022-01-28) — 1380 ms, 46.5 MB

public class Solution {
    public bool CanReach(int[] arr, int start) {
        List<int> seen = new List<int>();
    int n = arr.Length;
    if(arr[start] == 0) return true;
    Queue<int> q = new Queue<int>();
    q.Enqueue(start);
    seen.Add(start);
    while(q.Count != 0)
    {
        var popped = q.Dequeue();

        int left = popped - arr[popped];
        int right = popped + arr[popped];
        
        if(left >= 0 && !seen.Contains(left))
        {
            if(arr[left] == 0) return true;
            seen.Add(left);
            q.Enqueue(left);
        }
        if (right < n && !seen.Contains(right))
        {
            if(arr[right] == 0) return true;
            seen.Add(right);
            q.Enqueue(right);
        }
    }
    return false;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Think of BFS to solve the problem.

Hint 2: When you reach a position with a value = 0 then return true.