> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/42_trapping_rain_water.md).

# 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
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

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

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.