Trapping Rain Water | Python program to find maximum amount of water that can be trapped within given set of bars . Space Complexity : O ( 1 ) ; initialize output ; maximum element on left and right ; indices to traverse the array ; update max in left ; water on curr element = max - curr ; update right maximum ; Driver program
def findWater ( arr , n ) : NEW_LINE INDENT result = 0 NEW_LINE left_max = 0 NEW_LINE right_max = 0 NEW_LINE lo = 0 NEW_LINE hi = n - 1 NEW_LINE while ( lo <= hi ) : NEW_LINE INDENT if ( arr [ lo ] < arr [ hi ] ) : NEW_LINE INDENT if ( arr [ lo ] > left_max ) : NEW_LINE INDENT left_max = arr [ lo ] NEW_LINE DEDENT else : NEW_LINE INDENT result += left_max - arr [ lo ] NEW_LINE DEDENT lo += 1 NEW_LINE DEDENT else : NEW_LINE INDENT if ( arr [ hi ] > right_max ) : NEW_LINE INDENT right_max = arr [ hi ] NEW_LINE DEDENT else : NEW_LINE INDENT result += right_max - arr [ hi ] NEW_LINE DEDENT hi -= 1 NEW_LINE DEDENT DEDENT return result NEW_LINE DEDENT arr = [ 0 , 1 , 0 , 2 , 1 , 0 , 1 , 3 , 2 , 1 , 2 , 1 ] NEW_LINE n = len ( arr ) NEW_LINE print ( " Maximum ▁ water ▁ that ▁ can ▁ be ▁ accumulated ▁ is ▁ " , findWater ( arr , n ) ) NEW_LINE