Leetcode 1306. Jump Game III
Problem Explanation
We are given an array of non-negative integers and a start
index. At any index i
we can either move forward by arr[i]
or move backward by arr[i]
. We need to return a boolean indicating if we can reach at any 0
in the array or not. It is important to notice that the jumps should always leave the current index inside the array boundaries, i.e. 0 <= i < arr.length
.
Example
Let's take an example where we are given an array arr = [4,2,3,0,3,1,2]
and a start
index 5
. We can reach index 3
which has a 0
value as shown below:
index 5 -> index 4 -> index 1 -> index 3
Therefore, the output is True
.
Solution Explanation
This problem can be solved using Breadth-First Search (BFS) algorithm. We can add the start
index to a queue and start a loop that will continue till the queue is not empty. Inside the loop, we "visit" the node (index) at the front of the queue, and if the array value at the node is 0
, we return True
as we have reached our goal. We then check for the next nodes to be visited if this node does not have 0
. These nodes will be at the indices node + arr[node]
and node - arr[node]
, provided the indices lie within valid boundaries. We also maintain a seen
array to prevent cycles and revisiting nodes in the queue.
C++ Solution
1 2cpp 3class Solution { 4 public: 5 bool canReach(vector<int>& arr, int start) { 6 const int n = arr.size(); // getting size of array 7 queue<int> q{{start}}; // initializing queue with start index 8 vector<bool> seen(n); // boolean vector to track visited nodes 9 10 while (!q.empty()) { // continue while the queue is not empty 11 const int node = q.front(); 12 q.pop(); 13 14 if (arr[node] == 0) // if current node value is 0, return True 15 return true; 16 if (seen[node]) // if current node is already visited, continue to next iteration 17 continue; 18 19 // Check available next steps 20 if (node - arr[node] >= 0) // if valid, add (node - arr[node]) to queue 21 q.push(node - arr[node]); 22 if (node + arr[node] < n) // if valid, add (node + arr[node]) to queue 23 q.push(node + arr[node]); 24 25 seen[node] = true; // mark current node as visited 26 } 27 28 return false; // return false if the queue becomes empty and no 0 found 29 } 30};
Java Solution
1 2java 3class Solution { 4 public boolean canReach(int[] arr, int start) { 5 int n = arr.length; 6 Queue<Integer> q = new LinkedList<>(); 7 q.add(start); 8 boolean[] seen = new boolean[n]; 9 10 while (!q.isEmpty()) { 11 int node = q.poll(); 12 13 if (arr[node] == 0) 14 return true; 15 if (seen[node]) 16 continue; 17 18 if (node - arr[node] >= 0) 19 q.add(node - arr[node]); 20 if (node + arr[node] < n) 21 q.add(node + arr[node]); 22 23 seen[node] = true; 24 } 25 26 return false; 27 } 28}
Python Solution
1 2python 3class Solution: 4 def canReach(self, arr: List[int], start: int) -> bool: 5 n = len(arr) 6 q = [start] 7 seen = [False]*n 8 9 while q: 10 node = q.pop(0) 11 12 if arr[node] == 0: 13 return True 14 if seen[node]: 15 continue 16 17 if node - arr[node] >= 0: 18 q.append(node - arr[node]) 19 if node + arr[node] < n: 20 q.append(node + arr[node]) 21 22 seen[node] = True 23 24 return False
JavaScript Solution
1 2javascript 3var canReach = function(arr, start) { 4 const n = arr.length; 5 const queue = [start]; 6 const seen = Array(n).fill(false); 7 8 while(queue.length > 0) { 9 const node = queue.shift(); 10 11 if(arr[node] === 0) { 12 return true; 13 } 14 if(seen[node]) { 15 continue; 16 } 17 18 if(node - arr[node] >= 0) { 19 queue.push(node - arr[node]); 20 } 21 if(node + arr[node] < n) { 22 queue.push(node + arr[node]); 23 } 24 25 seen[node] = true; 26 } 27 28 return false; 29};
C# Solution
1 2csharp 3public class Solution { 4 public bool CanReach(int[] arr, int start) { 5 int n = arr.Length; 6 Queue<int> queue = new Queue<int>(); 7 queue.Enqueue(start); 8 bool[] visited = new bool[n]; 9 10 while(queue.Count > 0) { 11 int node = queue.Dequeue(); 12 13 if(arr[node] == 0) { 14 return true; 15 } 16 if(visited[node]) { 17 continue; 18 } 19 20 if(node - arr[node] >= 0) { 21 queue.Enqueue(node - arr[node]); 22 } 23 if(node + arr[node] < n) { 24 queue.Enqueue(node + arr[node]); 25 } 26 27 visited[node] = true; 28 } 29 30 return false; 31 } 32}
In all solutions so far, the depth-first or breadth-first searches are begun from the starting point and then all possible directions are added to the agenda, visited points are marked and the search continues until an index with 0
is found or if there are no new places to explore (if the queue is empty).
Breadth-first search starts traversing from the root node and visits nodes in a level by level manner. Each neighboring node is visited first before moving onto the next level nodes. In this problem, neighbors of a node come from steps forward or backward.
The main point here is to handle the constraints carefully. The step size is given by the current node and we have to make sure not to jump out of bounds as well as handle the issue that comes from cycles. Valid steps should be within the array bounds and hence, checking whether a position is valid simply requires a bounds check 0 <= i < arr.length
.
The time complexity of this algorithm is O(n), where n is the size of the input array. This is because in the worst case, we might have to process each element of the array once.
The space complexity is also O(n) as in the worst case we might have to add each element to the queue and also maintain its 'visited' state. Hence, space complexity is also linear.
Overall, this problem not only tests your basic understanding of traversal algorithms and some standard data structures but also tests your ability in dealing with constraints and corner cases.
Always keep in mind to first confirm the problem constraints (array bounds in this case) and also consider how to handle cyclical cases (using a visited array in this case) when dealing with any graph or array problems. Keep practicing and happy coding!
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.