Trapping Rain Water — Leetcode 42 [Hard]

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Intuition :

• Consider each point in the array, we can only store water if there is a wall on both sides.
• At each point, the maximum height it can store would be the minimum of the left wall height and right wall height.
• So, for each point, we keep track of the maximum left height and maximum right height for that point and then calculate water stored at that point as min(max_left_ht,max_right_ht) — height[i].

Approach 1 : O(n) Time complexity and O(n) Space complexity

• Maintain two arrays to store maximum left heights and maximum right heights for each data point.
• Calculate the current potential water level (curr_ht) as the minimum of the corresponding values from left_heights and right_heights for the current bar.
• Check if the curr_ht is greater than the current bar's height (height[i]). This indicates that there's trapped water.
• If there’s trapped water, the amount of trapped water for this bar (curr_ht - height[i]) is added to the result.

class Solution:
    def trap(self, height: List[int]) -> int:
        left_heights=[]
        right_heights=[]
        left_heights.append(0)
        max_height=0
        for i in range(1,len(height)):
            if height[i-1]>0 and max_height<height[i-1]:
                left_heights.append(height[i-1])
                max_height=max(max_height,height[i-1])
            else:
                left_heights.append(max_height)
        right_heights.append(0)
        max_height=0
        for i in range(len(height)-2,-1,-1):
            if height[i+1]>0 and max_height<height[i+1]:
                right_heights.append(height[i+1])
                max_height=max(max_height,height[i+1])
            else:
                right_heights.append(max_height)
        #print(left_heights)
        right_heights=right_heights[::-1]
        #print(right_heights)

        result=0
        results=[]
        for i in range(len(left_heights)):
            curr_ht=min(left_heights[i],right_heights[i])
            if curr_ht>height[i]:
                result+=curr_ht-height[i]
                results.append(curr_ht-height[i])
            else:
                results.append(0)
        #print(results)

        return result

Cons : The above approach has a space complexity of O(n). We can do it in O(1) space using two pointers approach.

Approach 2 : Two Pointers — O(n) time and O(1) space complexity

• Two pointers, i and j, are used:

i starts at the beginning of the height list (leftmost bar).

j starts at the end of the height list (rightmost bar)

• The maximum heights are updated for i and j. (left and right heights)
• Choose the side with lower maximum height
• The pointer on the side with smaller height is moved.

class Solution:
    def trap(self, height: List[int]) -> int:
        max_left_ht=0
        max_right_ht=0
        i=0
        j=len(height)-1
        result=0
        while i<=j:
            max_left_ht=max(max_left_ht,height[i])
            max_right_ht=max(max_right_ht,height[j])
            if max_left_ht<max_right_ht:
                if max_left_ht>height[i]:
                    result+=(max_left_ht-height[i])
                i+=1
            else:
                if max_right_ht>height[j]:
                    result+=(max_right_ht-height[j])
                j-=1
        return result