Minimum distance between any special pair in the given array | C ++ program for the above approach ; Function that finds the minimum difference between two vectors ; Find lower bound of the index ; Find two adjacent indices to take difference ; Return the result ; Function to find the minimum distance between index of special pairs ; Stores the index of each element in the array arr [ ] ; Store the indexes ; Get the unique values in list ; Take adjacent difference of same values ; Left index array ; Right index array ; Find the minimum gap between the two adjacent different values ; Driver Code ; Given array ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int mindist ( vector < int > & left , vector < int > & right ) { int res = INT_MAX ; for ( int i = 0 ; i < left . size ( ) ; ++ i ) { int num = left [ i ] ; int index = lower_bound ( right . begin ( ) , right . end ( ) , num ) - right . begin ( ) ; if ( index == 0 ) res = min ( res , abs ( num - right [ index ] ) ) ; else if ( index == right . size ( ) ) res = min ( res , abs ( num - right [ index - 1 ] ) ) ; else res = min ( res , min ( abs ( num - right [ index - 1 ] ) , abs ( num - right [ index ] ) ) ) ; } return res ; } int specialPairs ( vector < int > & nums ) { map < int , set < int > > m ; vector < int > vals ; for ( int i = 0 ; i < nums . size ( ) ; ++ i ) { m [ nums [ i ] ] . insert ( i ) ; } for ( auto p : m ) { vals . push_back ( p . first ) ; } int res = INT_MAX ; for ( int i = 0 ; i < vals . size ( ) ; ++ i ) { vector < int > vec ( m [ vals [ i ] ] . begin ( ) , m [ vals [ i ] ] . end ( ) ) ; for ( int i = 1 ; i < vec . size ( ) ; ++ i ) res = min ( res , abs ( vec [ i ] - vec [ i - 1 ] ) ) ; if ( i ) { int a = vals [ i ] ; vector < int > left ( m [ a ] . begin ( ) , m [ a ] . end ( ) ) ; int b = vals [ i - 1 ] ; vector < int > right ( m [ b ] . begin ( ) , m [ b ] . end ( ) ) ; res = min ( res , mindist ( left , right ) ) ; } } return res ; } int main ( ) { vector < int > arr { 0 , -10 , 5 , -5 , 1 } ; cout << specialPairs ( arr ) ; return 0 ; }