LC 42 - Trapping Rain Water

Question

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.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

Links

Question here and solution here

Solution

concept

The main concept here is to recognise that the amount of water can be trapped is evaluated by min(max(right of height[i]), max(left of height[i])) - height[i].
This make sense that the current location i is bounded by the maximum of either side but bottle necked by the minimum of the two.
We can iterate through the height array twice (suffix and prefix) to get the max of right and left, and then a third time to calculate the final water amount.
This is the $O(n)$ memory solution.

The $O(1)$ memory solution requires us to optimise from the min(max(right of height[i]), max(left of height[i])) - height[i] equation.
We can keep track of 2 variable maxLeft and maxRight , which keep track of the current max of left (of l pointer ) and max of right (or ) and deploy a two-pointer approach.
If the maxLeft is smaller than maxRight, l pointer will be moved to the left. Otherwise the r pointer is moved to the right.
Take note that since we are looking for the minimum of the maximum of the two side, this operations will ensure whichever side moved is the bottleneck and hence it is sufficient to look at either maxRight and maxLeft.

code

class MySolution:
	"""
	prefix and suffix array
	"""
    def trap(self, height: List[int]) -> int:
        # max left side
        left_max = []
        l_max = 0
        for i in range(len(height)):
            if i == 0:
                left_max.append(0)
            else:
                l_max = max(l_max, height[i - 1])
                left_max.append(l_max)

        # max right side
        right_max = []
        r_max = 0
        for i in range(len(height) - 1, -1, -1):
            if i == len(height) - 1:
                right_max.append(0)
            else:
                r_max = max(r_max, height[i + 1])
                right_max.append(r_max)
        right_max.reverse()

        # for every indx, we check min(max_right[i], max_right[i]) - height[i]
        # if positive, we know water can be trapped here
        ans = 0
        for i in range(len(height)):
            water = min(left_max[i], right_max[i]) - height[i]
            if water > 0:
                ans += water

        return ans

class NeetSolution:
	"""
	prefix and suffix array
	"""
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n == 0:
            return 0
        
        leftMax = [0] * n
        rightMax = [0] * n
        
        leftMax[0] = height[0]
        for i in range(1, n):
            leftMax[i] = max(leftMax[i - 1], height[i])
        
        rightMax[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], height[i])
        
        res = 0
        for i in range(n):
            res += min(leftMax[i], rightMax[i]) - height[i]
        return res

class Solution:
	"""
	
	"""
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        l, r = 0, len(height) - 1
        leftMax, rightMax = height[l], height[r]
        res = 0
        while l < r:
            if leftMax < rightMax:
                l += 1
                leftMax = max(leftMax, height[l])
                res += leftMax - height[l]
            else:
                r -= 1
                rightMax = max(rightMax, height[r])
                res += rightMax - height[r]
        return res

Complexity

time: $O(n)$
space: $O(n)$ or $O(1)$