Trapping Rain Water | Function to return the maximum water that can be stored ; Stores the indices of the bars ; size of the array ; Stores the final result ; Loop through the each bar ; Remove bars from the stack until the condition holds ; store the height of the top and pop it . ; If the stack does not have any bars or the the popped bar has no left boundary ; Get the distance between the left and right boundary of popped bar ; Calculate the min . height ; If the stack is either empty or height of the current bar is less than or equal to the top bar of stack ; Driver code
def maxWater ( height ) : NEW_LINE INDENT stack = [ ] NEW_LINE n = len ( height ) NEW_LINE ans = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT while ( len ( stack ) != 0 and ( height [ stack [ - 1 ] ] < height [ i ] ) ) : NEW_LINE INDENT pop_height = height [ stack [ - 1 ] ] NEW_LINE stack . pop ( ) NEW_LINE if ( len ( stack ) == 0 ) : NEW_LINE INDENT break NEW_LINE DEDENT distance = i - stack [ - 1 ] - 1 NEW_LINE min_height = min ( height [ stack [ - 1 ] ] , height [ i ] ) - pop_height NEW_LINE ans += distance * min_height NEW_LINE DEDENT stack . append ( i ) NEW_LINE DEDENT return ans NEW_LINE DEDENT arr = [ 0 , 1 , 0 , 2 , 1 , 0 , 1 , 3 , 2 , 1 , 2 , 1 ] NEW_LINE print ( maxWater ( arr ) ) NEW_LINE