Queries to find the minimum index in given array having at least value X | C ++ program to implement the above approach ; Function to find the smallest index of an array element whose value is less than or equal to Q [ i ] ; Stores size of array ; Stores coun of queries ; Store array elements along with the index ; Store smallest index of an array element whose value is greater than or equal to i ; Traverse the array ; Insert { arr [ i ] , i } into storeArrIdx [ ] ; Sort the array ; Sort the storeArrIdx ; Stores index of arr [ N - 1 ] in sorted order ; Traverse the array storeArrIdx [ ] ; Update minIdx [ i ] ; Traverse the array Q [ ] ; Store the index of lower_bound of Q [ i ] ; If no index found whose value greater than or equal to arr [ i ] ; Print smallest index whose value greater than or equal to Q [ i ] ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void minimumIndex ( vector < int > & arr , vector < int > & Q ) { int N = arr . size ( ) ; int M = Q . size ( ) ; vector < pair < int , int > > storeArrIdx ; vector < int > minIdx ( N ) ; for ( int i = 0 ; i < N ; ++ i ) { storeArrIdx . push_back ( { arr [ i ] , i } ) ; } sort ( arr . begin ( ) , arr . end ( ) ) ; sort ( storeArrIdx . begin ( ) , storeArrIdx . end ( ) ) ; minIdx [ N - 1 ] = storeArrIdx [ N - 1 ] . second ; for ( int i = N - 2 ; i >= 0 ; i -- ) { minIdx [ i ] = min ( minIdx [ i + 1 ] , storeArrIdx [ i ] . second ) ; } for ( int i = 0 ; i < M ; i ++ ) { int pos = lower_bound ( arr . begin ( ) , arr . end ( ) , Q [ i ] ) - arr . begin ( ) ; if ( pos == N ) { cout << -1 << " ▁ " ; continue ; } cout << minIdx [ pos ] << " ▁ " ; } } int main ( ) { vector < int > arr = { 1 , 9 } ; vector < int > Q = { 7 , 10 , 0 } ; minimumIndex ( arr , Q ) ; return 0 ; }