Maximum water that can be stored between two buildings | C ++ implementation of the above approach ; Return the maximum water that can be stored ; Make pairs with indices ; Sort array based on heights ; To store the min and max index so far from the right ; Current building paired with the building greater in height and on the extreme left ; Current building paired with the building greater in height and on the extreme right ; Maximum so far ; Update the maximum and minimum so far ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool compareTo ( pair < int , int > p1 , pair < int , int > p2 ) { return p1 . second < p2 . second ; } int maxWater ( int height [ ] , int n ) { pair < int , int > pairs [ n ] ; for ( int i = 0 ; i < n ; i ++ ) pairs [ i ] = make_pair ( i , height [ i ] ) ; sort ( pairs , pairs + n , compareTo ) ; int minIndSoFar = pairs [ n - 1 ] . first ; int maxIndSoFar = pairs [ n - 1 ] . first ; int maxi = 0 ; for ( int i = n - 2 ; i >= 0 ; i -- ) { int left = 0 ; if ( minIndSoFar < pairs [ i ] . first ) { left = ( pairs [ i ] . second * ( pairs [ i ] . first - minIndSoFar - 1 ) ) ; } int right = 0 ; if ( maxIndSoFar > pairs [ i ] . first ) { right = ( pairs [ i ] . second * ( maxIndSoFar - pairs [ i ] . first - 1 ) ) ; } maxi = max ( left , max ( right , maxi ) ) ; minIndSoFar = min ( minIndSoFar , pairs [ i ] . first ) ; maxIndSoFar = max ( maxIndSoFar , pairs [ i ] . first ) ; } return maxi ; } int main ( ) { int height [ ] = { 2 , 1 , 3 , 4 , 6 , 5 } ; int n = sizeof ( height ) / sizeof ( height [ 0 ] ) ; cout << maxWater ( height , n ) ; }