1306. Jump Game III

MediumDepth-First SearchBreadth-First SearchArray

Problem Description

You are given an array arr of non-negative integers and a starting index start. Your goal is to determine if you can jump to any index in the array where the value is 0. From each index i, you have two possible jumps: either i + arr[i] or i - arr[i]. However, you must stay within the bounds of the array; you cannot jump outside of it. The question is, can you find a path through the array, jumping from index to index, that leads you to an index whose value is 0?

Flowchart Walkthrough

Let's utilize the algorithm flowchart (see the Flowchart) to deduce the suitable algorithm for LeetCode's problem 1306, Jump Game III. Here's a step-by-step walkthrough:

Is it a graph?

Yes: Although not explicitly a typical graph, each index in the array can be viewed as a node with directed edges determined by the jump value at that index (forward or backward).

Is it a tree?

No: The structure can have cycles due to backward and forward jumps, which doesn't fit the definition of a tree.

Is the problem related to directed acyclic graphs (DAGs)?

No: The potential for cycles due to backward jumps eliminates it as a DAG.

Is the problem related to shortest paths?

No: The objective is to determine if we can reach an index with a value of 0, not to find the shortest path to any particular index.

Does the problem involve connectivity?

Yes: The core of the problem is to find out whether there is a path from a given start position to any position marked with a value of 0.

Does the problem have small constraints?

No: This decision is not strictly outlined here, but typically in DFS or BFS applicability doesn't strictly depend on small constraints unless specified in the problem explicitly for the algorithmic approach. For large indices counts, DFS is capable but might suffer from stack overflow recursion limits for very large depths, while BFS would require more substantial memory usage.

Is the graph weighted?

No: Each jump moves you an index positions forward or backward without any 'cost' associated beyond moving one step per index.

Conclusion: Following the flowchart and the problem's demands, Depth-First Search (DFS) is well-suited for exploring all possible index jumps, either recursively or using a stack, to check connectivity to a zero value. The choice between DFS and BFS might also be influenced by typical recursion depth practical limitations (in case of a deep DFS recursion). For Jump Game III, DFS can be efficiently used to explore different paths arising from each jump.

Intuition

The intuition behind solving this problem lies in considering it as a graph traversal problem, where each index is a node, and a jump represents an edge between nodes. Since we want to explore all possible jumping paths, we can use a Breadth-First Search (BFS) approach. BFS is especially useful here because it allows us to visit each node layer by layer, starting from the node we are given as start, and move onwards until we either find a node with the value 0 or exhaust all possible nodes that we can visit.

To implement BFS, we can use a queue to keep track of the indices we need to explore. For each index, we check whether the value is 0; if it is, we've reached our goal, and the answer is True. If the value is not 0, we "mark" this index as visited by setting its value to -1 to avoid revisiting it, which would cause an infinite loop. We then add the new indices we can jump to the queue if we have not visited them yet and they are within the bounds of the array. We continue this process until our queue is empty or we find a value of 0.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The solution utilizes the Breadth-First Search (BFS) algorithm to explore the array. The BFS algorithm is often used in graph traversal to visit nodes level by level, and in this case, it helps to find the shortest path to an index with value 0.

Here's how the implementation of the BFS algorithm works in the context of this problem:

We initiate a queue (deque in Python) and add the starting index to it. This queue holds the indices that we need to visit.
We enter a loop that continues until the queue is empty.
Inside the loop, we pop an index i from the front of the queue, which is the current index we are visiting.
We then check if the value at this index i is 0. If it is, it means we have successfully found a path to an index with value 0, and we return True.
If it's not 0, we consider it visited by marking arr[i] as -1. This prevents us from revisiting it because revisiting would mean we're going in circles and not exploring new possibilities.
We look at the indices we can jump to from index i, which are i + arr[i] and i - arr[i]. For each of these two indices, we check two conditions:
- The index must be within the bounds of the array (0 <= j < len(arr)).
- The value at that index must not have been visited (indicated by arr[j] >= 0).
If an index satisfies both conditions, we append it to the queue so we can visit it in a subsequent iteration.
Once we have processed all possible jumps from the current index and added any new indices to visit to our queue, we continue to the next iteration of the loop.
This process is repeated until either the queue is empty, which means we have visited all reachable indices and did not find a value of 0 (hence we return False), or we find an index with value 0.

By following the above steps, we utilize the BFS algorithm to check every index we can reach and determine if there is any path leading to an index with a value of 0.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a simple example:

Consider the input array arr = [4, 2, 3, 0, 3, 1, 2] and the starting index start = 5. Our target is to find out if by jumping left or right, starting from arr[5], we can reach an index with the value 0.

Following the BFS approach:

We initialize a queue and add the starting index 5 to it. Our queue now looks like this: [5].
Starting the loop, our queue is not empty.
We pop the first element from the queue, which is 5, and check the value of arr[5]. Since arr[5] = 1, it's not 0, so we continue.
We mark arr[5] as visited by setting it to -1. Now arr looks like this: [4, 2, 3, 0, 3, -1, 2].
We check the jump positions from index 5: 5 - arr[5] and 5 + arr[5] (before arr[5] was marked as -1). These positions are 5 - 1 = 4 and 5 + 1 = 6.
For the first jump position:
- Index 4 is within the bounds of the array and arr[4] = 3 (not visited yet), so we add index 4 to our queue. Our queue now looks like this: [4].
For the second jump position:
- Index 6 is also within the bounds and arr[6] = 2 (not visited), so we add index 6 to our queue. Our queue now: [4, 6].
We continue the loop, next popping index 4 from the queue. It's value is 3 (not 0), so we mark it as visited by setting arr[4] = -1. We examine the jump positions 4 + 3 = 7 (which is out of bounds) and 4 - 3 = 1.
- Index 1 is within bounds and arr[1] = 2 (not visited), so we add 1 to our queue. Queue: [6, 1].
The next index we pop from the queue is 6, and arr[6] was 2 before we mark it as visited (set to -1). We check the jump positions 6 + 2 = 8 (out of bounds) and 6 - 2 = 4, but since arr[4] is already visited (marked as -1), we don't add it to the queue. Queue remains the same: [1].
Next, we pop index 1 from the queue. Here we find arr[1] = 2, and after marking it visited, we check positions 1 + 2 = 3 and 1 - 2 = -1 (out of bounds). Index 3 is within bounds and arr[3] = 0. We've found a value of 0, so we immediately conclude our search with a True. We have found a path to an index with value 0.

Thus, by using the BFS algorithm, we efficiently navigated through the possible jump indices to find a path from start to an index where the value is 0.

Solution Implementation

1from collections import deque  # Make sure to import deque from collections
2
3class Solution:
4    def canReach(self, arr, start):
5        # Initialize a queue and add the start index to it
6        queue = deque([start])
7      
8        # Process nodes in the queue until it's empty
9        while queue:
10            # Pop the element from the queue
11            current_index = queue.popleft()
12          
13            # Check if the value at the current index is 0, if so we've reached the target and return True
14            if arr[current_index] == 0:
15                return True
16          
17            # Get the jump value from the array, which indicates how far we can jump from this index
18            jump_value = arr[current_index]
19          
20            # Mark this index as visited by setting its value to -1
21            arr[current_index] = -1
22          
23            # Calculate the indices for the next possible jumps (forward and backward)
24            for next_index in (current_index + jump_value, current_index - jump_value):
25                # Ensure the new index is within bounds and not already visited
26                if 0 <= next_index < len(arr) and arr[next_index] >= 0:
27                    # If valid and not visited, append this index to the queue for future processing
28                    queue.append(next_index)
29      
30        # If we've processed all possible indices and haven't returned True, then return False
31        return False
32

1class Solution {
2    public boolean canReach(int[] array, int start) {
3        // Queue to hold the indices to be checked
4        Deque<Integer> queue = new ArrayDeque<>();
5        queue.offer(start); // Begin from the starting index
6
7        // Continue until there are no more indices in the queue
8        while (!queue.isEmpty()) {
9            int currentIndex = queue.poll(); // Get the current index from the queue
10            // Check if the value at the current index is 0, meaning we've reached a target
11            if (array[currentIndex] == 0) {
12                return true; // We can reach an index with a value of 0
13            }
14            int jumpDistance = array[currentIndex]; // Store the jump distance from the current position
15            array[currentIndex] = -1; // Mark the current index as visited by setting it to -1
16
17            // Prepare the next indices to jump to (forward and backward)
18            int nextIndexForward = currentIndex + jumpDistance;
19            int nextIndexBackward = currentIndex - jumpDistance;
20
21            // Check if the forward jump index is within bounds and not yet visited
22            if (nextIndexForward >= 0 && nextIndexForward < array.length && array[nextIndexForward] >= 0) {
23                queue.offer(nextIndexForward); // If so, add it to the queue for later processing
24            }
25          
26            // Check if the backward jump index is within bounds and not yet visited
27            if (nextIndexBackward >= 0 && nextIndexBackward < array.length && array[nextIndexBackward] >= 0) {
28                queue.offer(nextIndexBackward); // If so, add it to the queue for later processing
29            }
30        }
31        return false; // If exited the loop, we weren't able to reach an index with a value of 0
32    }
33}
34

1#include <vector>
2#include <queue>
3
4class Solution {
5public:
6    // Determines if we can reach any index with value 0 starting from 'start' index
7    bool canReach(std::vector<int>& arr, int start) {
8        // Create a queue and initialize it with the start index
9        std::queue<int> indicesQueue;
10        indicesQueue.push(start);
11
12        // Use Breadth-First Search to explore the array
13        while (!indicesQueue.empty()) {
14            // Extract the current index from the queue
15            int currentIndex = indicesQueue.front();
16            indicesQueue.pop();
17
18            // If the value at the current index is 0, we've reached the target
19            if (arr[currentIndex] == 0) {
20                return true;
21            }
22
23            // Mark the current index as visited by setting its value to -1
24            int jumpValue = arr[currentIndex];
25            arr[currentIndex] = -1;
26
27            // Calculate the index positions we can jump to from the current index
28            int nextIndexForward = currentIndex + jumpValue;
29            int nextIndexBackward = currentIndex - jumpValue;
30
31            // If the next index is in bounds and hasn't been visited, add it to the queue
32            if (nextIndexForward >= 0 && nextIndexForward < arr.size() && arr[nextIndexForward] != -1) {
33                indicesQueue.push(nextIndexForward);
34            }
35            if (nextIndexBackward >= 0 && nextIndexBackward < arr.size() && arr[nextIndexBackward] != -1) {
36                indicesQueue.push(nextIndexBackward);
37            }
38        }
39
40        // If the queue is empty and we haven't returned true, then we cannot reach any index with value 0
41        return false;
42    }
43};
44

1function canReach(arr: number[], start: number): boolean {
2    // Create a queue for BFS and initialize with the start position
3    const queue: number[] = [start];
4  
5    // Process nodes until the queue is empty
6    while (queue.length > 0) {
7        // Dequeue an element from the queue
8        const currentIndex: number = queue.shift()!;
9      
10        // Check if the current index has a value of zero, indicating we can reach a zero value
11        if (arr[currentIndex] === 0) {
12            return true;
13        }
14      
15        // Get the jump value from the current position
16        const jumpValue: number = arr[currentIndex];
17      
18        // Mark the current position as visited by setting it to -1
19        arr[currentIndex] = -1;
20      
21        // Check both forward and backward jumps
22        for (const nextIndex of [currentIndex + jumpValue, currentIndex - jumpValue]) {
23            // Ensure the next index is within bounds and hasn't been visited yet
24            if (nextIndex >= 0 && nextIndex < arr.length && arr[nextIndex] !== -1) {
25                // Add the valid next index to the queue
26                queue.push(nextIndex);
27            }
28        }
29    }
30  
31    // Return false if we can't reach a value of zero in the array
32    return false;
33}
34

Time and Space Complexity

Time Complexity

The time complexity of the given code would be O(N), where N is the size of the array. This is because in the worst-case scenario we might need to visit each element in the array once. The code performs a Breadth-First Search (BFS) by iterating over the array and only traversing to those indices that haven't been visited yet (marked with -1).

Since we are checking each element to see if it is 0 (where the jump game ends), and the elements can only be added to the deque once (due to being marked as -1 after the first visit), the maximum number of operations is proportional to the number of elements in arr.

Space Complexity

The space complexity of the code is also O(N) due to the deque data structure that is used to store indices that need to be visited. In the worst case, this could store a number of indices up to the size of the arr.

The space complexity includes additional space for the deque and does not include the space taken up by the input itself. Since we are reusing the input array to mark visited elements, no additional space is needed for tracking visited positions outside of the input array and the deque.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know