42. Trapping Rain Water

Approach 1: Brute Force

class Solution:
    def trap(self, heights):
        """
        :type height: List[int]
        :rtype: int
        """
        ans = 0
        max_left, max_right = 0,0
        for index, height in enumerate(heights):
            ans += min(max(heights[:index+1]), max(heights[index:])) - height
        return ans

For each index, search for the maximum height to its left (max_left) and the maximum height of its right (max_right). For each index, the water it can hold is the minimum of the two max's minus the current level. This way you can get the total amount of water that can be held!

Time Complexity: O(N^2), where N is the length of the array

Space Complexity: O(1)

Approach 2: Memoise max

class Solution:
    def trap(self, heights):
        """
        :type height: List[int]
        :rtype: int
        """
        if len(heights) == 0:
            return 0
        ans = 0
        l, r = 0, len(heights) - 1
        ma_l, ma_r = heights[l], heights[r]
        while l < r:
            ma_l, ma_r = max(heights[l], ma_l), max(heights[r], ma_r)
            if ma_l <= ma_r:
                ans += ma_l - heights[l]
                l += 1
            else:
                ans += ma_r - heights[r]
                r -= 1
        return ans

Instead of recalculating the max's at each index we can memoise the two by storing the left max and the right max and only updating them when required. This way it reduces the time it takes for us to compute the max height to the left and to the right!

Time Complexity: O(N^2), where N is the length of the array

Space Complexity: O(1)