Given an array arr[ ] of size N consisting of integers -1, 0, 1 only and an array q[ ] consisting of queries. In the array arr[ ], -1 signifies that any index to the left of it is reachable and 1 signifies that any index to the right of it is reachable from that index. The index in a particular query is not directly reachable but all other indices are reachable. Find the minimum number of steps required to reach any index from it’s neighboring index (whichever is nearest) for each query and finally return the array of results. If any index is not reachable, return -1.
Examples:
Input: arr[ ] = {0, 0, -1, 0, 1, 0, 0, 1, 1, -1, 0}, q[ ] = {3, 6}
Output: result[ ] = {6, 2}
Explanation: There is only 1 way to reach index 3, i.e. from index 9. Therefore minimum distance= 9-3=6
The shortest path to reach index 6 is via index 4. Therefore minimum distance=6-4=2
result[ ]={6, 2}Input: arr[ ] = {-1, 0, 0, 0, 1}, q[ ] = {2, 0}
Output: result[ ] = {-1, 0}
Approach: The idea is to store the indices of nearest 1 from the left side and nearest -1 from the right side and then while traversing the array q[] for each query q[i], check for the distance from both sides and store the minimum one. Follow the steps to solve the problem:
- Initialize the vectors result[], v1[] and v2[] to store the result for each query, and the nearest 1 and -1.
- Initialize the variables last_1 and last_m1 as -1 to store the latest 1 and -1.
- Iterate over the range [0, N] using the variable i and perform the following tasks:
- Iterate over the range [N-1, 0] using the variable i and perform the following tasks:
- Reverse the vector v1[].
- Iterate over the range [0, M] using the variable i and perform the following tasks:
- If v1[q[i]] and v2[q[i]] are not equal to -1, then set the value result[i] as the minimum of abs(v1[q[i]] – q[i]) or abs(v2[q[i]] – q[i]).
- Else if, v1[q[i]] is not equal to -1, then set the value result[i] as abs(v1[q[i]] – q[i]).
- Else if, v2[q[i]] is not equal to -1, then set the value result[i] as abs(v2[q[i]] – q[i]).
- Else, set the value of result[i] as -1.
- After performing the above steps, print the vector result[] as the answer.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to return the min distance// from neighboring indexvector<int> res(int arr[], int q[], int n, int m){ // Vectors result, v1 and v2 to // store the minimum distance, index // of -1 and 1 respectively vector<int> result, v1, v2; // Variables to store the last // position of -1 and 1 int last_m1 = -1, last_1 = -1; // Traverse over the array arr[] // to store the index of 1 for (int i = 0; i < n; i++) { v2.push_back(last_1); if (arr[i] == 1) last_1 = i; } // Traverse over the array arr[] // to store the index of -1 for (int i = n - 1; i >= 0; i--) { v1.push_back(last_m1); if (arr[i] == -1) last_m1 = i; } // Reverse v1 to get the original order reverse(v1.begin(), v1.end()); // Traverse over the array q[] for (int i = 0; i < m; i++) { if (v1[q[i]] != -1 and v2[q[i]] != -1) result.push_back( min(abs(v1[q[i]] - q[i]), abs(v2[q[i]] - q[i]))); else if (v1[q[i]] != -1) result.push_back( abs(v1[q[i]] - q[i])); else if (v2[q[i]] != -1) result.push_back( abs(v2[q[i]] - q[i])); else result.push_back(-1); } // Finally return the vector of result return result;}// Driver Codeint main(){ // Input int arr[] = { -1, 0, 0, 1, -1, 1, 1, 0, 0, 1, -1, 0 }; int n = sizeof(arr) / sizeof(arr[0]); // Query int q[] = { 1, 5, 10 }; int m = sizeof(q) / sizeof(q[0]); // Function call to find the minimum distance vector<int> x = res(arr, q, n, m); // Print the resultant vector for (auto y : x) cout << y << " "; return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to return the min distance// from neighboring indexstatic Vector<Integer> res(int arr[], int q[], int n, int m){ // Vectors result, v1 and v2 to // store the minimum distance, index // of -1 and 1 respectively Vector<Integer> result = new Vector<Integer>(), v1= new Vector<Integer>(), v2= new Vector<Integer>(); // Variables to store the last // position of -1 and 1 int last_m1 = -1, last_1 = -1; // Traverse over the array arr[] // to store the index of 1 for (int i = 0; i < n; i++) { v2.add(last_1); if (arr[i] == 1) last_1 = i; } // Traverse over the array arr[] // to store the index of -1 for (int i = n - 1; i >= 0; i--) { v1.add(last_m1); if (arr[i] == -1) last_m1 = i; } // Reverse v1 to get the original order Collections.reverse(v1); // Traverse over the array q[] for (int i = 0; i < m; i++) { if (v1.get(q[i]) != -1 && v2.get(q[i]) != -1) result.add( Math.min(Math.abs(v1.get(q[i]) - q[i]), Math.abs(v2.get(q[i]) - q[i]))); else if (v1.get(q[i]) != -1) result.add( Math.abs(v1.get(q[i]) - q[i])); else if (v2.get(q[i]) != -1) result.add( Math.abs(v2.get(q[i]) - q[i])); else result.add(-1); } // Finally return the vector of result return result;}// Driver Codepublic static void main(String[] args){ // Input int arr[] = { -1, 0, 0, 1, -1, 1, 1, 0, 0, 1, -1, 0 }; int n = arr.length; // Query int q[] = { 1, 5, 10 }; int m = q.length; // Function call to find the minimum distance Vector<Integer> x = res(arr, q, n, m); // Print the resultant vector for (int y : x) System.out.print(y+ " ");}}// This code is contributed by shikhasingrajput |
Python3
# python program for the above approach# Function to return the min distance# from neighboring indexdef res(arr, q, n, m): # Vectors result, v1 and v2 to # store the minimum distance, index # of -1 and 1 respectively result = [] v1 = [] v2 = [] # Variables to store the last # position of -1 and 1 last_m1 = -1 last_1 = -1 # Traverse over the array arr[] # to store the index of 1 for i in range(0, n): v2.append(last_1) if (arr[i] == 1): last_1 = i # Traverse over the array arr[] # to store the index of -1 for i in range(n-1, -1, -1): v1.append(last_m1) if (arr[i] == -1): last_m1 = i # Reverse v1 to get the original order v1.reverse() # Traverse over the array q[] for i in range(0, m): if (v1[q[i]] != -1 and v2[q[i]] != -1): result.append(min(abs(v1[q[i]] - q[i]), abs(v2[q[i]] - q[i]))) elif (v1[q[i]] != -1): result.append(abs(v1[q[i]] - q[i])) elif (v2[q[i]] != -1): result.append(abs(v2[q[i]] - q[i])) else: result.push_back(-1) # Finally return the vector of result return result# Driver Codeif __name__ == "__main__": # Input arr = [-1, 0, 0, 1, -1, 1, 1, 0, 0, 1, -1, 0] n = len(arr) # Query q = [1, 5, 10] m = len(q) # Function call to find the minimum distance x = res(arr, q, n, m) # Print the resultant vector for y in x: print(y, end=" ") # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to return the min distance // from neighboring index static List<int> res(int[] arr, int[] q, int n, int m) { // Vectors result, v1 and v2 to // store the minimum distance, index // of -1 and 1 respectively List<int> result = new List<int>(); List<int> v1 = new List<int>(); List<int> v2 = new List<int>(); // Variables to store the last // position of -1 and 1 int last_m1 = -1, last_1 = -1; // Traverse over the array arr[] // to store the index of 1 for (int i = 0; i < n; i++) { v2.Add(last_1); if (arr[i] == 1) last_1 = i; } // Traverse over the array arr[] // to store the index of -1 for (int i = n - 1; i >= 0; i--) { v1.Add(last_m1); if (arr[i] == -1) last_m1 = i; } // Reverse v1 to get the original order v1.Reverse(); // Traverse over the array q[] for (int i = 0; i < m; i++) { if (v1[q[i]] != -1 && v2[q[i]] != -1) result.Add( Math.Min(Math.Abs(v1[q[i]] - q[i]), Math.Abs(v2[q[i]] - q[i]))); else if (v1[q[i]] != -1) result.Add(Math.Abs(v1[q[i]] - q[i])); else if (v2[q[i]] != -1) result.Add(Math.Abs(v2[q[i]] - q[i])); else result.Add(-1); } // Finally return the vector of result return result; } // Driver Code public static void Main() { // Input int[] arr = { -1, 0, 0, 1, -1, 1, 1, 0, 0, 1, -1, 0 }; int n = arr.Length; // Query int[] q = { 1, 5, 10 }; int m = q.Length; // Function call to find the minimum distance List<int> x = res(arr, q, n, m); // Print the resultant vector foreach(int y in x) Console.Write(y + " "); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to return the min distance // from neighboring index function res(arr, q, n, m) { // Vectors result, v1 and v2 to // store the minimum distance, index // of -1 and 1 respectively let result = [], v1 = [], v2 = []; // Variables to store the last // position of -1 and 1 let last_m1 = -1, last_1 = -1; // Traverse over the array arr[] // to store the index of 1 for (let i = 0; i < n; i++) { v2.push(last_1); if (arr[i] == 1) last_1 = i; } // Traverse over the array arr[] // to store the index of -1 for (let i = n - 1; i >= 0; i--) { v1.push(last_m1); if (arr[i] == -1) last_m1 = i; } // Reverse v1 to get the original order v1.reverse(); // Traverse over the array q[] for (let i = 0; i < m; i++) { if (v1[q[i]] != -1 && v2[q[i]] != -1) result.push( Math.min(Math.abs(v1[q[i]] - q[i]), Math.abs(v2[q[i]] - q[i]))); else if (v1[q[i]] != -1) result.push( Math.abs(v1[q[i]] - q[i])); else if (v2[q[i]] != -1) result.push( Math.abs(v2[q[i]] - q[i])); else result.push_back(-1); } // Finally return the vector of result return result; } // Driver Code // Input let arr = [-1, 0, 0, 1, -1, 1, 1, 0, 0, 1, -1, 0]; let n = arr.length; // Query let q = [1, 5, 10]; let m = q.length; // Function call to find the minimum distance let x = res(arr, q, n, m); // Print the resultant array for (let i = 0; i < x.length; i++) document.write(x[i] + " "); // This code is contributed by Potta Lokesh </script> |
Output
3 2 1
Time Complexity: O(N+M) where N is the size of arr[ ] and M is the size of q[ ]
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!
