# 42. Trapping Rain Water 🌧️

**Difficulty**: `Hard` - **Tags**: `Stack`, `Array`, `Two Pointers`, `Dynamic Programming`, `Monotonic Stack`

[LeetCode Problem Link](https://leetcode.com/problems/trapping-rain-water/description/)

## Description

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

![rainwatertrap](/files/fRGsCaHcao4HYFcVNYpV)

## Examples

**Example 1:**

Input:

```python
height = [0,1,0,2,1,0,1,3,2,1,2,1]
```

Output:

```
6
```

Explanation: The above elevation map (black section) is represented by the array `[0,1,0,2,1,0,1,3,2,1,2,1]`. In this case, 6 units of rainwater (blue section) are being trapped.

**Example 2:**

Input:

```python
height = [4,2,0,3,2,5]
```

Output:

```
9
```

## Constraints

* The length of `height` is in the range `[0, 2 * 10^4]`.
* Each element in `height` is a non-negative integer in the range `[0, 10^5]`.

## Solution 💡

To solve this problem, we can visualize the elevation map as a mountain with a highest peak. By calculating the amount of water that can be trapped from both edges towards the peak, we can determine the total trapped water:

1. Initialize two pointers (`left` and `right`) at both ends of the array and two variables to track the maximum height seen from both ends.
2. Move the pointers towards each other, calculating the trapped water based on the minimum of the two maximum heights.

### Java

```java
class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int waterTrapped = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    waterTrapped += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    waterTrapped += rightMax - height[right];
                }
                right--;
            }
        }

        return waterTrapped;
    }
}
```

### Time Complexity ⏳

* The time complexity is **O(n)**, where `n` is the number of elements in `height`.

### Space Complexity 💾

* The space complexity is **O(1)**, as we only use a few variables for tracking.

You can find the full solution [here](https://github.com/ChunhThanhDe/Leetcode-Top-Interview/blob/main/Topic%201%20Array%20-%20String/016%20Trapping%20Rain%20Water/Solution.java) of another solution [here](https://github.com/ChunhThanhDe/Leetcode-Top-Interview/blob/main/Topic%201%20Array%20-%20String/016%20Trapping%20Rain%20Water/AnotherSolution.java).


---

# 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://chunhthanhde.gitbook.io/leetcode-top-interview/topic-1-array-string/016-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.