LC 42 & LC 85

Solution to LeetCode 42 Trapping Rain Water and LeetCode 84

LeetCode 42

Trapping Rain Water (Hard) [link]

1] Brute Force Solution: Double Pointers (ETL). Calculate height column by column. The height of rain water depends on the lowest bar between the left and right bars. i.e. The height of rain water at certain position is min(lHeight, rHeight) - height. Note that the first and the last bar don’t trap train water.

Time complexity is O(n^2).

class Solution:
    def trap(self, height: List[int]) -> int:
        res = 0
        for i in range(len(height)):
            if i == 0 or i == len(height)-1:
                continue
            lH = height[i-1]
            rH = height[i+1]
            for j in range(i-1):
                if height[j] > lH:
                    lH = height[j]
            for j in range(i+2, len(height)):
                if height[j] > rH:
                    rH = height[j]
            cur = min(lH, rH) - height[i]
            if cur >= 0:
                res += cur
        return res

2] Dynamic Programming. Notice that by applying double pointers method, there are duplicated calculations. To avoid duplicated calculations, we can record the max left height into a maxLeft array, and the max right height into a maxRight array.

The max left height of the current bar, is the max of (max left height of the bar on the left, its height). Therefore, we can fulfill the array maxLeft by iterating from left to the right: maxLeft[i] = max(height[i], maxLeft[i - 1]) and fulfill the array maxRight by iterating from right to the left: maxRight[i] = max(height[i], maxRight[i + 1]).

Time complexity O(n).

class Solution:
    def trap(self, height: List[int]) -> int:
        lH = [0] * len(height)
        rH = [0] * len(height)
        res = 0
        
        lH[0] = height[0]
        for i in range(1, len(height)):
            lH[i] = max(lH[i-1], height[i])
        
        rH[-1] = height[-1]
        for i in range(len(height)-2, -1, -1):
            rH[i] = max(rH[i+1], height[i])
        
        for i in range(len(height)):
            cur = min(lH[i], rH[i]) - height[i]
            res += cur
        return res

LeetCode 84

Largest Rectangle in Histogram (Hard) [link]

1] Brute Force Solution: Double Pointers (ELT). The idea is that for each bar, find the closest lower bar to the left and to the right, so the width can be determined. Then calculate the height[i]*width.

Time complexity O(n^2).

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        res = 0
        for i in range(len(heights)):
            left = i
            right = i
            for _ in range(left, -1, -1):
                if heights[left] < heights[i]:
                    break
                left -= 1
            for _ in range(right, len(heights)):
                if heights[right] < heights[i]:
                    break
                right += 1

            width = right - left - 1
            res = max(res, width * heights[i])
        return res

2] Dynamic Programming. The idea is to first construct two arrays storing the index of the closest lower bar to the ith bar. Then reuse the two arrays to find the max area.

Time complexity O(n).

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        lH = [0] * len(heights)
        rH = [0] * len(heights)
        res = 0
        lH[0] = -1 # avoid endless while loop
        for i in range(1, len(heights)):
            temp = i-1
            while temp >=0 and heights[temp] >= heights[i]:
                temp = lH[temp]
            lH[i] = temp

        rH[-1] = len(heights) # avoid endless while loop
        for i in range(len(heights)-2, -1, -1):
            temp = i+1
            while temp < len(heights) and heights[temp] >= heights[i]:
                temp = rH[temp]
            rH[i] = temp

        for i in range(len(heights)):
            width = rH[i]-lH[i]-1
            res = max(res, heights[i] * width)
        return res