Intuition

This problem uses a very similar solution to 135. Candy.

Important point to notice is: water can’t be at the edges, the edge is either 0 heigh (water leak) or wall with no water on top. So with this in mind we can ignore water on edges.

The volume of water in any place is water = max_height - current_height.

Let’s take this example [0,2,0,3,0,2], the # represents the walls, the . represents the water.

    #
  #.#.#
__#.#.#

From left to right, this would be the result:

   #..
 #.#.#
_#.#.#

From right to left, this would be the result:

...#
.#.#.#
.#.#.#

With this visualization, now it’s clear that we need a two pass solution, and the result would be the minimum of L and R arrays.

Approach

Left pass, store the different between current_height and current_max. Right pass, store the different between current_height and current_max.

The answer is the minimum of the two arrays.

Complexity

• Time complexity: O(n)

• Space complexity: O(n)

Code

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """

        m = len(height)
        L=[0] * m
        R=[0] * m

        curr_max = height[0]
        for i in range(1,m):
            if height[i] < curr_max:
                L[i] = curr_max - height[i]
            else:
                curr_max = height[i]

        curr_max = height[m-1]
        for i in reversed(range(m-1)):
            if height[i] < curr_max:
                R[i] = curr_max - height[i]
            else:
                curr_max = height[i]
                
        return sum(min(L[i],R[i]) for i in range(m))