Solution For Jump Game Iv
Problem Description:
Given an array of integers arr, you are initially positioned at the first index of the array.
In one step you can jump from index i to index:
- i + 1 where: i + 1 < arr.length.
- i – 1 where: i – 1 >= 0.
- j where: arr[i] == arr[j] and i != j.
Return the minimum number of steps to reach the last index of the array.
Notice that you can not jump outside of the array at any time.
Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 –> 4 –> 3 –> 9. Note that index 9 is the last index of the array.
Approach:
To solve this problem, we can use a BFS approach, where we start from the first index and keep adding indices to a queue. The queue will initially only contain the first index, and the distance to reach it will be 0. We will keep track of visited indices to avoid revisiting them.
At each step, we will explore all the possible jumps from the current index, which include jumps to indices i+1, i-1 and all indices with the same value as arr[i]. We will add all unvisited indices to the queue, along with their distance (which will be the distance of the current index + 1). The search will continue until we reach the last index of the array.
To optimize the search, we can use a dictionary to keep track of all occurrences of each value in the array and the indices at which they occur. This will help us quickly find all indices we can jump to with a single jump.
Solution:
We start by initializing the queue with the first index and the distance to reach it (0). We also initialize a visited set to keep track of visited indices.
We then create a dictionary to store all the indices where each value in the array occurs.
Next, we enter into a while loop which will continue until the queue is empty (all indices have been visited) or we reach the last index of the array. At each iteration, we get the current index and its distance from the queue. We check if the current index is the last index of the array, and if it is, we return its distance.
Otherwise, we explore all the possible jumps from the current index. For each possible jump, we check if the index is within the bounds of the array and if it has not been previously visited. If both conditions are met, we add the index to the queue along with its distance.
To find all indices with the same value as the current index, we use the dictionary we created earlier to quickly look up all occurrences of the current value in the array. We then add all unvisited indices to the queue along with their distance.
Finally, we mark the current index as visited and continue with the next index in the queue.
If we have exhausted all possible jumps from the current index and have not reached the last index of the array, we return -1 (it is not possible to reach the last index).
Time Complexity:
As we are using BFS, the time complexity will be O(n) where n is the number of elements in the array. Each index will be visited at most once, and each jump from an index can be made in constant time using the dictionary.
Space Complexity:
The space complexity will also be O(n), as we are using a queue to store the indices and a set to keep track of visited indices. We are also using a dictionary to store the occurrences of each value in the array. The maximum size of the dictionary can be O(n) if all values in the array are distinct.
Step by Step Implementation For Jump Game Iv
class Solution {
public int minJumps(int[] arr) {
int n = arr.length;
if (n == 1)
return 0;
// Create a map to store jumps
HashMap map
= new HashMap();
// Create an array to track visited index
boolean[] visited = new boolean[n];
// Create a queue for BFS
Queue queue = new LinkedList();
// Mark the start index as visited
visited[0] = true;
queue.add(0);
int level = 0;
while (!queue.isEmpty()) {
// Check if there are elements in the queue
int size = queue.size();
// Perform the BFS steps
for (int i = 0; i < size; i++) {
int curr = queue.poll();
// Check if we have reached the end
if (curr == n - 1)
return level;
// Get the element at the current index
int element = arr[curr];
// Check if this element has already been visited
// If not, mark it as visited and enqueue it
if (!visited[element]) {
visited[element] = true;
queue.add(element);
}
// Check if there is an entry for this index
// If not, mark it as visited and enqueue it
if (!map.containsKey(curr)) {
visited[curr] = true;
queue.add(curr);
}
}
// Go to the next level
level++;
}
// If we reach here, it means we have not
// been able to reach the end
return -1;
}
} class Solution:
def minJumps(self, arr: List[int]) -> int:
# create a dict to store the indices of each value
value_indices = collections.defaultdict(list)
for i, v in enumerate(arr):
value_indices[v].append(i)
# create a queue for BFS
queue = collections.deque([0])
visited = set()
steps = 0
# do BFS
while queue:
for _ in range(len(queue)):
curr = queue.popleft()
if curr == len(arr) - 1:
return steps
if curr in visited:
continue
visited.add(curr)
# add indices within reachable range
for i in range(max(0, curr - 1), min(curr + 2, len(arr))):
if i not in visited:
queue.append(i)
# add indices reachable by same value
for index in value_indices[arr[curr]]:
if index not in visited:
queue.append(index)
# remove indices of same value so we don't revisit them
value_indices[arr[curr]] = []
steps += 1
return -1//Solution:
var jump = function(nums) {
//Create a queue to keep track of the indices that need to be visited
let queue = [];
//Create a visited set to keep track of which indices have already been visited
let visited = new Set();
//Add the first index to the queue
queue.push(0);
//Add the first index to the visited set
visited.add(0);
//Create a variable to keep track of the number of jumps needed
let jumps = 0;
//While the queue is not empty, keep looping
while (queue.length > 0) {
//Get the size of the queue
let size = queue.length;
//Loop through the queue
for (let i = 0; i < size; i++) {
//Get the first element in the queue
let curr = queue.shift();
//If the current element is the last element in the array, return the number of jumps needed
if (curr == nums.length - 1) {
return jumps;
}
//Loop through the current element's neighbors
for (let j = 1; j <= nums[curr]; j++) {
//Calculate the index of the neighbor
let next = curr + j;
//If the neighbor has not been visited yet, add it to the queue and the visited set
if (!visited.has(next)) {
queue.push(next);
visited.add(next);
}
}
}
//Increment the number of jumps
jumps++;
}
};class Solution {
public:
int minJumps(vector& arr) {
int n = arr.size();
// Create a map to store solutions of already
// computed subproblems
unordered_map dp;
// Create an array of pairs where first element
// is an element from array and second element
// is position of first element
queue > q;
for (int i = 0; i < n; i++)
q.push(make_pair(arr[i], i));
// Mark the element which are visited
vector visited(n, false);
visited[0] = true;
// Variable to check if destination is
// reached or not
int dest = n - 1;
// Perform BFS starting from first element
while (!q.empty())
{
// Remove an element from queue
pair k = q.front();
q.pop();
// If this is destination element,
// return its distance
if (k.second == dest)
return dp[dest];
// Getting all the indexes where arr[k.second]
// can jump
vector temp = getIndexes(k.second, k.first);
// Loop for all the indexes
for (int i = 0; i < temp.size(); i++)
{
// If this index is not visited and can
// lead to destination, push it into
// the queue with distance incremented by 1.
if (!visited[temp[i]])
{
q.push(make_pair(arr[temp[i]], temp[i]));
dp[temp[i]] = dp[k.second] + 1;
visited[temp[i]] = true;
}
}
}
}
}; class Solution {
public int Jump(int[] arr) {
int[] dp = new int[arr.Length];
for (int i = 1; i < arr.Length; i++) {
dp[i] = int.MaxValue;
}
for (int i = 0; i < arr.Length; i++) {
for (int j = 1; j <= arr[i]; j++) {
if (i + j < arr.Length) {
dp[i + j] = Math.Min(dp[i + j], dp[i] + 1);
}
}
}
return dp[arr.Length - 1];
}
}