Jump Game Iv

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]; 
    } 
}


Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]