Trapping Rain Water | Function to return the maximum water that can be stored ; indices to traverse the array ; To store Left max and right max for two pointers left and right ; To store the total amount of rain water trapped ; We need check for minimum of left and right max for each element ; Add the difference between current value and right max at index r ; Update right max ; Update right pointer ; Add the difference between current value and left max at index l ; Update left max ; Update left pointer ; Driver code
def maxWater ( arr , n ) : NEW_LINE INDENT left = 0 NEW_LINE right = n - 1 NEW_LINE l_max = 0 NEW_LINE r_max = 0 NEW_LINE result = 0 NEW_LINE while ( left <= right ) : NEW_LINE INDENT if r_max <= l_max : NEW_LINE INDENT result += max ( 0 , r_max - arr [ right ] ) NEW_LINE r_max = max ( r_max , arr [ right ] ) NEW_LINE right -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT result += max ( 0 , l_max - arr [ left ] ) NEW_LINE l_max = max ( l_max , arr [ left ] ) NEW_LINE left += 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 ( maxWater ( arr , n ) ) NEW_LINE