Find the farthest smaller number in the right side | C ++ implementation of the approach ; Function to find the farthest smaller number in the right side ; To store minimum element in the range i to n ; If current element in the suffix_min is less than a [ i ] then move right ; Print the required answer ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void farthest_min ( int a [ ] , int n ) { int suffix_min [ n ] ; suffix_min [ n - 1 ] = a [ n - 1 ] ; for ( int i = n - 2 ; i >= 0 ; i -- ) { suffix_min [ i ] = min ( suffix_min [ i + 1 ] , a [ i ] ) ; } for ( int i = 0 ; i < n ; i ++ ) { int low = i + 1 , high = n - 1 , ans = -1 ; while ( low <= high ) { int mid = ( low + high ) / 2 ; if ( suffix_min [ mid ] < a [ i ] ) { ans = mid ; low = mid + 1 ; } else high = mid - 1 ; } cout << ans << " ▁ " ; } } int main ( ) { int a [ ] = { 3 , 1 , 5 , 2 , 4 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; farthest_min ( a , n ) ; return 0 ; }