Given an array arr[] of size N, the task is to find the minimum number of jumps to reach the last index of the array starting from index 0. In one jump you can move from current index i to index j, if arr[i] = arr[j] and i != j or you can jump to (i + 1) or (i – 1).
Note: You can not jump outside of the array at any time.
Examples:
Input: arr = {100, -23, -23, 404, 100, 23, 23, 23, 3, 404}
Output: 3
Explanation: Valid jump indices are 0 -> 4 -> 3 -> 9.Input: arr = {7, 6, 9, 6, 9, 6, 9, 7}
Output: 1
An approach using BFS:
Here consider the elements which are at (i + 1), (i – 1), and all elements similar to arr[i] and insert them into a queue to perform BFS. Repeat the BFS in this manner and keep the track of level. When the end of array is reached return the level value.
Follow the steps below to implement the above idea:
- Initialize a map for mapping elements with the indices of their occurrence.
- Initialize a queue and an array visited[] to keep track of the elements that are visited.
- Push starting element into the queue and mark it as visited
- Initialize a variable count for counting the minimum number of valid jumps to reach the last index
- Do the following while the queue size is greater than 0:
- Iterate on all the elements of the queue
- Fetch the front element and pop out from the queue
- Check if we reach the last index or not
- If true, then return the count
- Check if curr + 1 is a valid position to visit or not
- If true, push curr + 1 into the queue and mark it as visited
- Check if curr – 1 is a valid position to visit or not
- If true, push curr – 1 into the queue and mark it as visited
- Now, Iterate over all the elements that are similar to curr
- Check if the child is in a valid position to visit or not
- If true, push the child into the queue and mark it as visited
- Check if the child is in a valid position to visit or not
- Erase all the occurrences of curr from the map because we already considered these elements for a valid jump in the above step
- Increment the count of jump
- Iterate on all the elements of the queue
- Finally, return the count.
Below is the implementation of the above approach.
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to find the// minimum number of jumps requiredint minimizeJumps(vector<int>& arr){ int n = arr.size(); // Initialize a map for mapping element // with indices of all similar value // occurrences in array unordered_map<int, vector<int> > unmap; // Mapping element with indices for (int i = 0; i < n; i++) { unmap[arr[i]].push_back(i); } queue<int> q; vector<bool> visited(n, false); // Push starting element into queue // and mark it visited q.push(0); visited[0] = true; // Initialize a variable count for // counting the minimum number number // of valid jump to reach at last index int count = 0; // Do while queue size is // greater than 0 while (q.size() > 0) { int size = q.size(); // Iterate on all the // elements of queue for (int i = 0; i < size; i++) { // Fetch the front element and // pop out from queue int curr = q.front(); q.pop(); // Check if we reach at the // last index or not if true, // then return the count if (curr == n - 1) { return count; } // Check if curr + 1 is valid // position to visit or not if (curr + 1 < n && visited[curr + 1] == false) { // If true, push curr + 1 // into queue and mark // it as visited q.push(curr + 1); visited[curr + 1] = true; } // Check if curr - 1 is valid // position to visit or not if (curr - 1 >= 0 && visited[curr - 1] == false) { // If true, push curr - 1 // into queue and mark // it as visited q.push(curr - 1); visited[curr - 1] = true; } // Now, Iterate over all the // element that are similar // to curr for (auto child : unmap[arr[curr]]) { if (curr == child) continue; // Check if child is valid // position to visit or not if (visited[child] == false) { // If true, push child // into queue and mark // it as visited q.push(child); visited[child] = true; } } // Erase all the occurrences // of curr from map. Because // we already considered these // element for valid jump // in above step unmap.erase(arr[curr]); } // Increment the count of jump count++; } // Finally, return the count. return count;}// Driver codeint main(){ vector<int> arr = { 100, -23, -23, 404, 100, 23, 23, 23, 3, 404 }; // Function Call cout << minimizeJumps(arr); return 0;} |
Java
// Java code for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find the minimum // number of jumps required static int minimizeJumps(int[] arr) { int n = arr.length; // Initialize a map for mapping element // with indices of all similar value // occurrences in array HashMap<Integer, List<Integer> > unmap = new HashMap<>(); // Mapping element with indices for (int i = 0; i < n; i++) { if (unmap.containsKey(arr[i])) { unmap.get(arr[i]).add(i); } else { List<Integer> temp = new ArrayList<>(); temp.add(i); unmap.put(arr[i], temp); } } Queue<Integer> q = new LinkedList<>(); boolean[] visited = new boolean[n]; Arrays.fill(visited, false); // Push starting element into queue // and mark it visited q.add(0); visited[0] = true; // Initialize a variable count for // counting the minimum number number // of valid jump to reach at last index int count = 0; // Do while queue size is // greater than 0 while (q.size() > 0) { int size = q.size(); // Iterate on all the // elements of queue for (int i = 0; i < size; i++) { // Fetch the front element and // pop out from queue int curr = q.poll(); // Check if we reach at the // last index or not if true, // then return the count if (curr == n - 1) { return count / 2; } // Check if curr + 1 is valid // position to visit or not if (curr + 1 < n && visited[curr + 1] == false) { // If true, push curr + 1 // into queue and mark // it as visited q.add(curr + 1); visited[curr + 1] = true; } // Check if curr - 1 is valid // position to visit or not if (curr - 1 >= 0 && visited[curr - 1] == false) { // If true, push curr - 1 // into queue and mark // it as visited q.add(curr - 1); visited[curr - 1] = true; } // Now, Iterate over all the // element that are similar // to curr if (unmap.containsKey(arr[i])) { for (int j = 0; j < unmap.get(arr[curr]).size(); j++) { int child = unmap.get(arr[curr]).get(j); if (curr == child) { continue; } // Check if child is valid // position to visit or not if (visited[child] == false) { // If true, push child // into queue and mark // it as visited q.add(child); visited[child] = true; } } } // Erase all the occurrences // of curr from map. Because // we already considered these // element for valid jump // in above step unmap.remove(arr[curr]); } // Increment the count of jump count++; } // Finally, return the count. return count / 2; } public static void main(String[] args) { int[] arr = { 100, -23, -23, 404, 100, 23, 23, 23, 3, 404 }; // Function call System.out.print(minimizeJumps(arr)); }}// This code is contributed by lokesh |
Python3
# Python code to implement the above approach# Function to find the# minimum number of jumps requireddef minimizeJumps(arr): n = len(arr) # Initialize a map for mapping element # with indices of all similar value # occurrences in array unmap = {} # Mapping element with indices for i in range(n): if arr[i] in unmap: unmap.get(arr[i]).append(i) else: unmap.update({arr[i]:[i]}) q = [] visited = [False]*n # Push starting element into queue # and mark it visited q.append(0) visited[0] = True # Initialize a variable count for # counting the minimum number number # of valid jump to reach at last index count = 0 # Do while queue size is # greater than 0 while(len(q) > 0): size = len(q) # Iterate on all the # elements of queue for i in range(size): # Fetch the front element and # pop out from queue curr = q[0] q.pop(0) # Check if we reach at the # last index or not if true, # then return the count if(curr == n - 1): return count//2 # Check if curr + 1 is valid # position to visit or not if(curr + 1 < n and visited[curr + 1] == False): # If true, push curr + 1 # into queue and mark # it as visited q.append(curr + 1) visited[curr + 1] = True # Check if curr - 1 is valid # position to visit or not if(curr - 1 >= 0 and visited[curr - 1] == False): # If true, push curr - 1 # into queue and mark # it as visited q.append(curr - 1) visited[curr - 1] = True # Now, Iterate over all the # element that are similar # to curr if arr[i] in unmap: for j in range(len(unmap[arr[curr]])): child=unmap.get(arr[curr])[j] if(curr==child): continue # Check if child is valid # position to visit or not if(visited[child] == False): # If true, push child # into queue and mark # it as visited q.append(child) visited[child] = True # Erase all the occurrences # of curr from map. Because # we already considered these # element for valid jump # in above step if arr[curr] in unmap: unmap.pop(arr[curr]) # Increment the count of jump count = count + 1 # Finally, return the count. return count//2# Driver codearr=[100, -23, -23, 404, 100, 23, 23, 23, 3, 404]# Function Callprint(minimizeJumps(arr))# This code is contributed by Pushpesh Raj. |
C#
// C# code for the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to find the minimum// number of jumps requiredstatic int minimizeJumps(int[] arr){ int n = arr.Length; // Initialize a map for mapping element // with indices of all similar value // occurrences in array Dictionary<int,List<int>> unmap = new Dictionary<int,List<int>>(); // Mapping element with indices for (int i = 0; i < n; i++) { if (unmap.ContainsKey(arr[i])) { unmap[arr[i]].Add(i); } else { List<int> temp = new List<int>(); temp.Add(i); unmap.Add(arr[i],temp); } } List<int> q = new List<int>(); bool[] visited = new bool[n]; for(int i=0;i<n;i++) { visited[i]=false; } // Push starting element into queue // and mark it visited q.Add(0); visited[0] = true; // Initialize a variable count for // counting the minimum number number // of valid jump to reach at last index int count = 0; // Do while queue size is // greater than 0 while (q.Count > 0) { int size = q.Count; // Iterate on all the // elements of queue for (int i = 0; i < size; i++) { // Fetch the front element and // pop out from queue int curr = q[0]; q.RemoveAt(0); // Check if we reach at the // last index or not if true, // then return the count if (curr == n - 1) { return count / 2; } // Check if curr + 1 is valid // position to visit or not if (curr + 1 < n && visited[curr + 1] == false) { // If true, push curr + 1 // into queue and mark // it as visited q.Add(curr + 1); visited[curr + 1] = true; } // Check if curr - 1 is valid // position to visit or not if (curr - 1 >= 0 && visited[curr - 1] == false) { // If true, push curr - 1 // into queue and mark // it as visited q.Add(curr - 1); visited[curr - 1] = true; } // Now, Iterate over all the // element that are similar // to curr if (unmap.ContainsKey(arr[i])){ for (int j = 0; j < unmap[arr[curr]].Count; j++) { int child= unmap[arr[curr]][j]; if (curr == child) { continue; } // Check if child is valid // position to visit or not if (visited[child] == false) { // If true, push child // into queue and mark // it as visited q.Add(child); visited[child] = true; } } } // Erase all the occurrences // of curr from map. Because // we already considered these // element for valid jump // in above step unmap.Remove(arr[curr]); } // Increment the count of jump count++; } // Finally, return the count. return count / 2;} static public void Main (string[] args){ int[] arr = { 100, -23, -23, 404, 100, 23, 23, 23, 3, 404 }; // Function call Console.WriteLine(minimizeJumps(arr)); }}// This code is contributed by Aman Kumar |
Javascript
// JavaScript code for the above approach// Function to find the// minimum number of jumps requiredfunction minimizeJumps(arr){ let n = arr.length; // Initialize a map for mapping element // with indices of all similar value // occurrences in array let unmap = new Map(); // Mapping element with indices for (let i = 0; i < n; i++) { if (unmap.has(arr[i])) unmap.get(arr[i]).push(i); else unmap.set(arr[i], [i]); } let q = []; let visited = new Array(n).fill(0); // Push starting element into queue // and mark it visited q.push(0); visited[0] = true; // Initialize a variable count for // counting the minimum number number // of valid jump to reach at last index let count = 0; // Do while queue size is // greater than 0 while (q.length > 0) { let size = q.length; // Iterate on all the // elements of queue for (let i = 0; i < size; i++) { // Fetch the front element and // pop out from queue let curr = q.shift(); // Check if we reach at the // last index or not if true, // then return the count if (curr == n - 1) { return count / 2; } // Check if curr + 1 is valid // position to visit or not if (curr + 1 < n && visited[curr + 1] == false) { // If true, push curr + 1 // into queue and mark // it as visited q.push(curr + 1); visited[curr + 1] = true; } // Check if curr - 1 is valid // position to visit or not if (curr - 1 >= 0 && visited[curr - 1] == false) { // If true, push curr - 1 // into queue and mark // it as visited q.push(curr - 1); visited[curr - 1] = true; } // Now, Iterate over all the // element that are similar // to curr if (unmap.has(arr[i])) { for (let i = 0; i < unmap.get(arr[curr]).length; i++) { child = unmap.get(arr[curr])[i]; if (curr == child) continue; // Check if child is valid // position to visit or not if (visited[child] == false) { // If true, push child // into queue and mark // it as visited q.push(child); visited[child] = true; } } } // Erase all the occurrences // of curr from map. Because // we already considered these // element for valid jump // in above step unmap.delete(arr[curr]); } // Increment the count of jump count++; } // Finally, return the count. return count / 2;}// Driver codelet arr = [ 100, -23, -23, 404, 100, 23, 23, 23, 3, 404 ];// Function Callconsole.log(minimizeJumps(arr));// This code is contributed by Potta Lokesh |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
