Trapping rain water problem in O(n) time and O(1) space.

trapping_rain_water.py

# Problem here -> https://leetcode.com/problems/trapping-rain-water/

height = [0,1,0,2,1,0,1,3,2,1,2,1]   # Elevation map

lm, rm = 0, 0
left, right = 0, len(height)-1
water = 0
        
while left<right:
    if height[left]>lm: lm = height[left]
    if height[right]>rm: rm = height[right]    
    if lm < rm:
        water += max(0, lm-height[left])
        left+=1
    else:
        water += max(0, rm-height[right])
        right-=1

print(water)

# Time complexity = O(n)
# Space complexity = O(1)