# 42 Trapping Rain Water

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

For example,

```
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
```

![](/files/-LoJIj9IULvi_JuX8O-b)

**The Idea:** First we have to understand details about the nature of the problem. The first question we have to answer is: when does a 'tower' was water on top of it? This is only true when their exists a left tower and a right tower that have a greater height that it. Gravity would otherwise flush the water down either end. The second question is: how much water can be stored on top of a tower? The answer to that is the `min(maxLeftTower, maxRightTower) - currentTower`. We are only interested in the minimum because the amount of water that can be stored will at most be the height of the shortest tower. Then subtract the height of the current tower because it serves as an offset from the floor or ground zero.

We can create a hash table that stores the `maxLeft`and `maxRight`tower locations. If there doesn't exist a tower with a greater height, we denote it with -1 (these are include in the ends of the array).

![](/files/-LoJIj9KJJJBX25kWbDn)

**Complexity:** O(3n) time and O(2n) extra space

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

        size = len(height)
        if not height:
            return 0

        max_right = {size - 1: -1}
        max_left = {0: -1}
        cur_max = height[size - 1]

        for i in range(len(height) - 2, -1, -1):
            if height[i] > cur_max:
                cur_max = height[i]
                max_right[i] = -1
            else:
                max_right[i] = cur_max

        cur_max = height[0]
        for i in range(0, size):
            if height[i] > cur_max:
                cur_max = height[i]
                max_left[i] = -1
            else:
                max_left[i] = cur_max

        return sum([min(max_right[i], max_left[i]) - height[i]
                    for i in range(0, size) if max_right[i] != -1 and max_left[i] != -1])
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/42_trapping_rain_water.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.