# 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 HashMapmap = 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]; } }