Minimum Steps to Reach the Target using BFS
We can find the minimum number of steps to reach the target element of the array starting from index 0 by performing a Breadth-First Search (BFS). In each step, consider elements at (i + 1), (i – 1), and all elements equal to arr[i], and insert them into a queue. Keep track of the level during BFS, and when we reach the target value of the array, return the level value as the minimum number of steps.
Step-by-step approach:
- Initialize a map to store element indices.
- Initialize a queue and an visited array to track visited elements.
- Push the start element into the queue and mark it as visited.
- Initialize a count for minimum valid steps.
- While the queue is not empty:
- For each element in the queue:
- Pop the front element as curr.
- If it’s the target value, return the count.
- Check and push (curr + 1) and (curr – 1) if valid positions.
- For all elements similar to curr:
- Push valid children into the queue.
- Erase all occurrences of curr in the map.
- Increment the step count.
- For each element in the queue:
- 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 steps required int minimizeJumps(vector< int >& arr, int target, int K) { int n = arr.size(); // Initilize 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 steps to reach at target value 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 // target value or not if true, // then return the count if (arr[curr] == target) { return count; } // Check if curr + K is valid // position to visit or not if (curr + K < n && visited[curr + 1] == false ) { // If true, push curr + 1 // into queue and mark // it as visited q.push(curr + K); visited[curr + K] = true ; } // Check if curr - K is valid // position to visit or not if (curr - K >= 0 && visited[curr - K] == false ) { // If true, push curr - 1 // into queue and mark // it as visited q.push(curr - K); visited[curr - K] = 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 steps // in above step unmap.erase(arr[curr]); } // Increment the count of steps count++; } // Finally, return the count. return count; } // Driver code int main() { vector< int > arr = { 60, -23, -23, 300, 60, 23, 23, 23, 3, 300 }; int target = 300, K = 1; // Function Call cout << minimizeJumps(arr, target, K); return 0; } |
Java
import java.util.*; public class Main { // Function to find the minimum number of steps required static int minimizeJumps(List<Integer> arr, int target, int K) { int n = arr.size(); // Initialize a map for mapping element // with indices of all similar value // occurrences in the array Map<Integer, List<Integer> > unmap = new HashMap<>(); // Mapping element with indices for ( int i = 0 ; i < n; i++) { unmap .computeIfAbsent(arr.get(i), k -> new ArrayList<>()) .add(i); } Queue<Integer> q = new LinkedList<>(); boolean [] visited = new boolean [n]; // Push the starting element into the queue // and mark it visited q.offer( 0 ); visited[ 0 ] = true ; // Initialize a variable count for counting // the minimum number of valid steps to reach // the target value int count = 0 ; // Do while the queue size is greater than 0 while (!q.isEmpty()) { int size = q.size(); // Iterate on all the elements of the queue for ( int i = 0 ; i < size; i++) { // Fetch the front element and pop it out // from the queue int curr = q.poll(); // Check if we reach the target value // if true, then return the count if (arr.get(curr) == target) { return count; } // Check if curr + K is a valid position to // visit or not if (curr + K < n && !visited[curr + K]) { // If true, push curr + 1 into the queue // and mark it as visited q.offer(curr + K); visited[curr + K] = true ; } // Check if curr - K is a valid position to // visit or not if (curr - K >= 0 && !visited[curr - K]) { // If true, push curr - 1 into the queue // and mark it as visited q.offer(curr - K); visited[curr - K] = true ; } // Now, iterate over all the elements that // are similar to curr for ( int child : unmap.getOrDefault( arr.get(curr), Collections.emptyList())) { if (curr == child) { continue ; } // Check if child is a valid position to // visit or not if (!visited[child]) { // If true, push child into the // queue and mark it as visited q.offer(child); visited[child] = true ; } } // Erase all the occurrences of curr from // the map because we already considered // these elements for valid steps unmap.remove(arr.get(curr)); } // Increment the count of steps count++; } // Finally, return the count. return count; } // Driver code public static void main(String[] args) { List<Integer> arr = Arrays.asList( 60 , - 23 , - 23 , 300 , 60 , 23 , 23 , 23 , 3 , 300 ); int target = 300 , K = 1 ; // Function Call System.out.println(minimizeJumps(arr, target, K)); } } |
Python3
from collections import deque # Function to find the minimum number of steps required def minimize_jumps(arr, target, K): n = len (arr) # Initialize a dictionary 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] not in unmap: unmap[arr[i]] = [] unmap[arr[i]].append(i) q = deque() 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 of valid steps to reach the target value 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 it from queue curr = q.popleft() # Check if we reach the target value or not # If true, then return the count if arr[curr] = = target: return count # Check if curr + K is a valid position to visit or not if curr + K < n and not visited[curr + K]: # If true, push curr + K into queue and mark it as visited q.append(curr + K) visited[curr + K] = True # Check if curr - K is a valid position to visit or not if curr - K > = 0 and not visited[curr - K]: # If true, push curr - K into queue and mark it as visited q.append(curr - K) visited[curr - K] = True # Now, Iterate over all the elements that are similar to curr if arr[curr] in unmap: for child in unmap[arr[curr]]: if curr = = child: continue # Check if child is a valid position to visit or not if not visited[child]: # If true, push child into queue and mark it as visited q.append(child) visited[child] = True # Erase all the occurrences of curr from the dictionary. # Because we already considered these elements for valid steps # in the above step unmap.pop(arr[curr]) # Increment the count of steps count + = 1 # Finally, return the count return count # Driver code arr = [ 60 , - 23 , - 23 , 300 , 60 , 23 , 23 , 23 , 3 , 300 ] target = 300 K = 1 # Function Call print (minimize_jumps(arr, target, K)) |
C#
using System; using System.Collections.Generic; using System.Linq; public class GFG { // Function to find the minimum number // of steps required static int MinimizeJumps(List< int > arr, int target, int K) { int n = arr.Count; // Initialize a dictionary for mapping element // with indices of all similar value // occurrences in the 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]] = new List< int >(); unmap[arr[i]].Add(i); } Queue< int > q = new Queue< int >(); bool [] visited = new bool [n]; // Push the starting element into the queue // and mark it visited q.Enqueue(0); visited[0] = true ; // Initialize a variable count for counting // the minimum number of valid steps to reach // the target value int count = 0; // Do while the queue size is greater than 0 while (q.Count > 0) { int size = q.Count; // Iterate on all the elements of the queue for ( int i = 0; i < size; i++) { // Fetch the front element and dequeue it int curr = q.Dequeue(); // Check if we reach the target value // if true, then return the count if (arr[curr] == target) { return count; } // Check if curr + K is a valid position to // visit or not if (curr + K < n && !visited[curr + K]) { // If true, push curr + K into the queue // and mark it as visited q.Enqueue(curr + K); visited[curr + K] = true ; } // Check if curr - K is a valid position to // visit or not if (curr - K >= 0 && !visited[curr - K]) { // If true, push curr - K into the queue // and mark it as visited q.Enqueue(curr - K); visited[curr - K] = true ; } // Now, iterate over all the elements that // are similar to curr if (unmap.TryGetValue( arr[curr], out List< int > childList)) { foreach ( int child in childList) { if (curr == child) { continue ; } // Check if child is a valid // position to visit or not if (!visited[child]) { // If true, push child into the // queue and mark it as visited q.Enqueue(child); visited[child] = true ; } } // Erase all the occurrences of curr // from the map because we already // considered these elements for valid // steps unmap.Remove(arr[curr]); } // Erase all the occurrences of curr from // the map because we already considered // these elements for valid steps unmap.Remove(arr[curr]); } // Increment the count of steps count++; } // Finally, return the count. return count; } // Driver code public static void Main( string [] args) { List< int > arr = new List< int >{ 60, -23, -23, 300, 60, 23, 23, 23, 3, 300 }; int target = 300, K = 1; // Function Call Console.WriteLine(MinimizeJumps(arr, target, K)); } } |
Javascript
// JavaScript Implementation of the given problem // Function to find the minimum // number of steps required function minimizeJumps(arr, target, K) { const n = arr.length; // Initialize a map for mapping element // with indices of all similar value // occurrences in array const unmap = new Map(); // Mapping element with indices for (let i = 0; i < n; i++) { if (!unmap.has(arr[i])) { unmap.set(arr[i], []); } unmap.get(arr[i]).push(i); } const q = []; const visited = new Array(n).fill( 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 of valid steps let count = 0; // Loop while queue has elements while (q.length > 0) { const size = q.length; // Iterate on all the elements of queue for (let i = 0; i < size; i++) { // Fetch the front element and // dequeue it from the queue const curr = q.shift(); // Check if we reach the target value if (arr[curr] === target) { return count; } // Check if curr + K is a valid // position to visit if (curr + K < n && !visited[curr + K]) { q.push(curr + K); visited[curr + K] = true ; } // Check if curr - K is a valid // position to visit if (curr - K >= 0 && !visited[curr - K]) { q.push(curr - K); visited[curr - K] = true ; } // Iterate over all the elements // that are similar to curr if (unmap.has(arr[curr])) { for (const child of unmap.get(arr[curr])) { if (curr === child) continue ; if (!visited[child]) { q.push(child); visited[child] = true ; } } // Erase all the occurrences // of curr from map unmap. delete (arr[curr]); } } // Increment the count of steps count++; } // Return the count return count; } // Driver code const arr = [60, -23, -23, 300, 60, 23, 23, 23, 3, 300]; const target = 300; const K = 1; // Function Call console.log(minimizeJumps(arr, target, K)); |
2
Time Complexity: O(N), where N is the number of elements in the given array.
Auxiliary Space: O(N)
Minimum Steps to Reach the Target
Given an array arr[] of size N and two integer values target and K, the task is to find the minimum number of steps required to reach the target element starting from index 0. In one step, you can either:
- Move from the current index i to index j if arr[i] is equal to arr[j] and i != j.
- Move to (i + k) or (i – k).
Note: It is not allowed to move outside of the array at any time.