# Trapping Rain Water
**Difficulty:** HARD
[External](https://leetcode.com/problems/trapping-rain-water)
Canonical: https://scaleengineer.com/dsa/problems/trapping-rain-water
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [Accolite](https://scaleengineer.com/companies/accolite), [Adobe](https://scaleengineer.com/companies/adobe), [Airbnb](https://scaleengineer.com/companies/airbnb), [Amazon](https://scaleengineer.com/companies/amazon), [American Express](https://scaleengineer.com/companies/american-express), [Apple](https://scaleengineer.com/companies/apple), [Atlassian](https://scaleengineer.com/companies/atlassian), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [ByteDance](https://scaleengineer.com/companies/bytedance), [Capgemini](https://scaleengineer.com/companies/capgemini), [Cisco](https://scaleengineer.com/companies/cisco), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Expedia](https://scaleengineer.com/companies/expedia), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Intel](https://scaleengineer.com/companies/intel), [Intuit](https://scaleengineer.com/companies/intuit), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Myntra](https://scaleengineer.com/companies/myntra), [Nutanix](https://scaleengineer.com/companies/nutanix), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [Paytm](https://scaleengineer.com/companies/paytm), [Publicis Sapient](https://scaleengineer.com/companies/publicis-sapient), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Roblox](https://scaleengineer.com/companies/roblox), [SAP](https://scaleengineer.com/companies/sap), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Snowflake](https://scaleengineer.com/companies/snowflake), [Tekion](https://scaleengineer.com/companies/tekion), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [jio](https://scaleengineer.com/companies/jio), [tcs](https://scaleengineer.com/companies/tcs), [Zopsmart](https://scaleengineer.com/companies/zopsmart), [MAQ Software](https://scaleengineer.com/companies/maq-software), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Salesforce](https://scaleengineer.com/companies/salesforce), [Tesla](https://scaleengineer.com/companies/tesla), [Zeta](https://scaleengineer.com/companies/zeta), [Citadel](https://scaleengineer.com/companies/citadel), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Swiggy](https://scaleengineer.com/companies/swiggy), [Zenefits](https://scaleengineer.com/companies/zenefits), [Media.net](https://scaleengineer.com/companies/media.net), [PhonePe](https://scaleengineer.com/companies/phonepe), [Zepto](https://scaleengineer.com/companies/zepto), [BitGo](https://scaleengineer.com/companies/bitgo), [carwale](https://scaleengineer.com/companies/carwale), [X](https://scaleengineer.com/companies/x), [Coveo](https://scaleengineer.com/companies/coveo), [HashedIn](https://scaleengineer.com/companies/hashedin), [Sprinklr](https://scaleengineer.com/companies/sprinklr), [Jane Street](https://scaleengineer.com/companies/jane-street), [PubMatic](https://scaleengineer.com/companies/pubmatic), [Nextdoor](https://scaleengineer.com/companies/nextdoor), [Splunk](https://scaleengineer.com/companies/splunk), [Grammarly](https://scaleengineer.com/companies/grammarly), [InMobi](https://scaleengineer.com/companies/inmobi), [Navi](https://scaleengineer.com/companies/navi), [CrowdStrike](https://scaleengineer.com/companies/crowdstrike), [Groww](https://scaleengineer.com/companies/groww), [Hive](https://scaleengineer.com/companies/hive), [Moloco](https://scaleengineer.com/companies/moloco), [National Instruments](https://scaleengineer.com/companies/national-instruments), [Navan](https://scaleengineer.com/companies/navan), [Turvo](https://scaleengineer.com/companies/turvo), [redbus](https://scaleengineer.com/companies/redbus)
---
## Problem
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.

**Example 1:**

![](https://assets.glich.co/dsa/trapping-rain-water/image0.png) 

**Input:** 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 array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

**Example 2:**

**Input:** height = [4,2,0,3,2,5]
**Output:** 9

**Constraints:**

* `n == height.length`
* `1 <= n <= 2 * 104`
* `0 <= height[i] <= 105`

# Approaches
## Brute Force Approach
This is the most straightforward approach. For each bar, we find the highest bar on its left and its right. The amount of water that can be trapped above the current bar is the minimum of these two heights minus the current bar's height.
**Time:** O(n^2) · **Space:** O(1)
**Pros:** Simple to understand and implement.; Uses constant extra space.
**Cons:** Highly inefficient due to repeated calculations for `maxLeft` and `maxRight` for each bar.; Likely to result in a 'Time Limit Exceeded' error on larger test cases.
### Explanation
The core idea is that the water trapped at any position `i` is determined by the walls around it. Specifically, it's `min(max_left_height, max_right_height) - height[i]`. In this approach, we iterate through each bar of the elevation map (excluding the first and last, as they cannot trap water by themselves). For each bar at index `i`, we perform two additional scans: one to find the maximum height of all bars to its left (including itself), and another to find the maximum height of all bars to its right (including itself). The water level at position `i` is limited by the lower of these two maximums. We calculate the trapped water at `i` and add it to a running total.

```java
class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int n = height.length;
        int totalWater = 0;
        // Iterate through each bar from index 1 to n-2
        for (int i = 1; i < n - 1; i++) {
            // Find the maximum height to the left of the current bar
            int maxLeft = 0;
            for (int j = i; j >= 0; j--) {
                maxLeft = Math.max(maxLeft, height[j]);
            }
            
            // Find the maximum height to the right of the current bar
            int maxRight = 0;
            for (int j = i; j < n; j++) {
                maxRight = Math.max(maxRight, height[j]);
            }
            
            // Water trapped at current bar is min(maxLeft, maxRight) - height[i]
            totalWater += Math.min(maxLeft, maxRight) - height[i];
        }
        return totalWater;
    }
}
```
### Algorithm
- Initialize a variable `totalWater` to 0.
- Iterate through the `height` array from the second element to the second-to-last element (indices `1` to `n-2`). Let the current index be `i`.
- For each index `i`:
    - Find the maximum height to the left of `i` (including `i`). Iterate from index `0` to `i` and find `maxLeft`.
    - Find the maximum height to the right of `i` (including `i`). Iterate from index `i` to `n-1` and find `maxRight`.
    - The water that can be trapped at index `i` is `min(maxLeft, maxRight) - height[i]`.
    - If this value is positive, add it to `totalWater`.
- Return `totalWater`.

## Dynamic Programming with Pre-computation
This approach optimizes the brute-force method by pre-calculating the maximum heights. Instead of re-calculating the left and right maximums for each bar, we store them in two separate arrays. This reduces the overall time complexity from quadratic to linear.
**Time:** O(n) · **Space:** O(n)
**Pros:** Efficient linear time complexity.; Conceptually a clear improvement over brute force.
**Cons:** Requires extra space proportional to the input size for the two arrays.
### Explanation
The bottleneck in the brute-force approach is the repeated scanning to find `maxLeft` and `maxRight`. We can eliminate this redundancy by pre-computing these values for every index and storing them. We create two arrays, `leftMax` and `rightMax`. `leftMax[i]` will store the maximum height from index 0 to `i`, and `rightMax[i]` will store the maximum height from index `i` to `n-1`.
`leftMax` can be filled with a single pass from left to right. `rightMax` can be filled with a single pass from right to left.
Once these arrays are populated, we can iterate through the `height` array one more time. For each index `i`, the trapped water is simply `min(leftMax[i], rightMax[i]) - height[i]`.

```java
class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int n = height.length;
        int totalWater = 0;
        
        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(height[i], leftMax[i - 1]);
        }
        
        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(height[i], rightMax[i + 1]);
        }
        
        for (int i = 0; i < n; i++) {
            totalWater += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        
        return totalWater;
    }
}
```
### Algorithm
- Create an array `leftMax` of size `n`.
- Fill `leftMax`: `leftMax[i]` is the maximum height from `height[0]` to `height[i]`.
- Create an array `rightMax` of size `n`.
- Fill `rightMax`: `rightMax[i]` is the maximum height from `height[i]` to `height[n-1]`.
- Initialize `totalWater = 0`.
- Iterate from `i = 0` to `n-1`:
    - Add `min(leftMax[i], rightMax[i]) - height[i]` to `totalWater`.
- Return `totalWater`.

## Two Pointers Approach
This is the most optimal solution, achieving linear time complexity with constant space. It uses two pointers, one at the beginning and one at the end of the array, that move towards each other. This method avoids the need for extra storage arrays by processing the bars and calculating trapped water on the fly.
**Time:** O(n) · **Space:** O(1)
**Pros:** Optimal solution with O(n) time and O(1) space.; Efficient and elegant.
**Cons:** The logic can be slightly more complex to understand initially compared to the DP approach.
### Explanation
This approach optimizes the space complexity of the DP solution. Instead of storing the `leftMax` and `rightMax` for all elements in arrays, we can compute the trapped water in a single pass using two pointers, `left` and `right`, starting at the two ends of the array. We also maintain `leftMax` and `rightMax` variables, which track the maximum height encountered so far from the left and right ends, respectively.
At each step, we compare `height[left]` and `height[right]`.
If `height[left]` is smaller, we know that the water level at the `left` pointer is determined by `leftMax`, because `rightMax` is guaranteed to be at least `height[right]`, which is greater than `height[left]`. We can then calculate the trapped water at `left` as `leftMax - height[left]` and move `left` one step to the right.
If `height[right]` is smaller or equal, a similar logic applies to the `right` pointer. We calculate trapped water as `rightMax - height[right]` and move `right` one step to the left.
The process continues until the pointers meet.

```java
class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int n = height.length;
        int left = 0, right = n - 1;
        int leftMax = 0, rightMax = 0;
        int totalWater = 0;
        
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    totalWater += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    totalWater += rightMax - height[right];
                }
                right--;
            }
        }
        
        return totalWater;
    }
}
```
### Algorithm
- Initialize `left = 0`, `right = n-1`, `leftMax = 0`, `rightMax = 0`, and `totalWater = 0`.
- Loop while `left < right`:
    - If `height[left] < height[right]`:
        - If `height[left] >= leftMax`, update `leftMax = height[left]`.
        - Else, add `leftMax - height[left]` to `totalWater`.
        - Increment `left`.
    - Else (`height[right] <= height[left]`):
        - If `height[right] >= rightMax`, update `rightMax = height[right]`.
        - Else, add `rightMax - height[right]` to `totalWater`.
        - Decrement `right`.
- Return `totalWater`.

# Solutions
### CSharp

```csharp
public class Solution { public int Trap ( int [] height ) { int n = height . Length ; int [] left = new int [ n ]; int [] right = new int [ n ]; left [ 0 ] = height [ 0 ]; right [ n - 1 ] = height [ n - 1 ]; for ( int i = 1 ; i < n ; ++ i ) { left [ i ] = Math . Max ( left [ i - 1 ], height [ i ]); right [ n - i - 1 ] = Math . Max ( right [ n - i ], height [ n - i - 1 ]); } int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { ans += Math . Min ( left [ i ], right [ i ]) - height [ i ]; } return ans ; } }
```

### Java

```java
public class Trapping_Rain_Water { public static void main ( String [] args ) { Trapping_Rain_Water out = new Trapping_Rain_Water (); Solution_local_minimum s = out . new Solution_local_minimum (); System . out . println ( s . trap ( new int []{ 5 , 2 , 1 , 2 , 1 , 5 })); } // The short board effect, the storage capacity is related to the short board of the bucket. // Find the longest slab in the height array, and then iterate from both ends to the long slab. When encountering a shorter one, find the storage capacity, and when encountering a longer one, update the edge. public class Solution_optimize { public int trap ( int [] height ) { if ( height == null || height . length == 0 ) return 0 ; int sum = 0 ; int maxind = 0 ; int max = Integer . MIN_VALUE ; // find max index for ( int i = 0 ; i < height . length ; i ++) { if ( height [ i ] > max ) { max = height [ i ]; maxind = i ; } } // left int leftmax = height [ 0 ]; for ( int i = 1 ; i < maxind ; i ++) { if ( leftmax < height [ i ]) { leftmax = height [ i ]; } sum += leftmax - height [ i ]; } // right int rightmax = height [ height . length - 1 ]; for ( int i = height . length - 2 ; i > maxind ; i --) { if ( rightmax < height [ i ]) { rightmax = height [ i ]; } sum += rightmax - height [ i ]; } return sum ; } } // local minimum solution is NOT doable. like [5,2,1,2,1,5], there are 2 local minimums with each holding 1 water // but they are just part of a global minimum class Solution_local_minimum { public int trap ( int [] height ) { // for each position, probe to left and right, find local minimum if ( height == null || height . length == 0 ) return 0 ; int sum = 0 ; int i = 1 ; // index=0 or index=length-1 will not be a local min, since nothing on its left to hold water while ( i < height . length - 1 ) { // only process local min index if ( height [ i ] < height [ i - 1 ] && height [ i ] < height [ i + 1 ]) { int left = i - 1 ; while ( left - 1 >= 0 && height [ left ] < height [ left - 1 ]) { left --; } int right = i + 1 ; while ( right + 1 < height . length && height [ right ] < height [ right + 1 ]) { right ++; } // now find its highest bar on both sides int lower = Math . min ( height [ left ], height [ right ]); // add up while ( left < right ) { if ( height [ left ] < lower ) { sum += lower - height [ left ]; } left ++; } // update pointer to search next local minimum i = right ; } else { i ++; } } return sum ; } } } ////// class Solution_notFindingMaxHeight { public int trap ( int [] height ) { if ( height == null || height . length == 0 ) return 0 ; int length = height . length ; int [] leftMax = new int [ length ]; // `leftMax` represents the maximum height in the subarray from the leftmost index to the current index int [] rightMax = new int [ length ]; // `rightMax` represents the maximum height in the subarray from the current index to the rightmost index leftMax [ 0 ] = height [ 0 ]; for ( int i = 1 ; i < length ; i ++) leftMax [ i ] = Math . max ( height [ i ], leftMax [ i - 1 ]); rightMax [ length - 1 ] = height [ length - 1 ]; for ( int i = length - 2 ; i >= 0 ; i --) rightMax [ i ] = Math . max ( height [ i ], rightMax [ i + 1 ]); int amount = 0 ; for ( int i = 0 ; i < length ; i ++) amount += Math . min ( leftMax [ i ], rightMax [ i ]) - height [ i ]; return amount ; } } ////// class Solution { public int trap ( int [] height ) { int n = height . length ; if ( n < 3 ) { return 0 ; } int [] lmx = new int [ n ]; int [] rmx = new int [ n ]; lmx [ 0 ] = height [ 0 ]; rmx [ n - 1 ] = height [ n - 1 ]; for ( int i = 1 ; i < n ; ++ i ) { lmx [ i ] = Math . max ( lmx [ i - 1 ], height [ i ]); rmx [ n - 1 - i ] = Math . max ( rmx [ n - i ], height [ n - i - 1 ]); } int res = 0 ; for ( int i = 0 ; i < n ; ++ i ) { res += Math . min ( lmx [ i ], rmx [ i ]) - height [ i ]; } return res ; } }
```

### Python

```python
class Solution:
    def trap(self, height: List[int]) -> int: n = len(height) if n < 3: return 0 lmx = [height[0]] * n rmx = [height[n - 1]] * n for i in range(1, n): lmx[i] = max(lmx[i - 1], height[i])  # i self compare rmx [ n - 1 - i ] = max ( rmx [ n - i ], height [ n - 1 - i ]) # no negative, worst is, min(left,right) is itself return sum ( min ( lmx [ i ], rmx [ i ]) - height [ i ] for i in range ( n ) ) ###### class Solution : # zip def trap ( self , height : List [ int ]) -> int : n = len ( height ) left = [ height [ 0 ]] * n right = [ height [ - 1 ]] * n for i in range ( 1 , n ): left [ i ] = max ( left [ i - 1 ], height [ i ]) right [ n - i - 1 ] = max ( right [ n - i ], height [ n - i - 1 ]) return sum ( min ( l , r ) - h for l , r , h in zip ( left , right , height )) ###### class Solution : # find the highest bar first def trap ( self , height : List [ int ]) -> int : if not height : return 0 total_water = 0 max_index = 0 max_height = float ( '-inf' ) # Find the index of the maximum height for i in range ( len ( height )): if height [ i ] > max_height : max_height = height [ i ] max_index = i # Calculate water trapped on the left side of the maximum height left_max = height [ 0 ] for i in range ( 1 , max_index ): if left_max < height [ i ]: left_max = height [ i ] total_water += left_max - height [ i ] # Calculate water trapped on the right side of the maximum height right_max = height [ - 1 ] for i in range ( len ( height ) - 2 , max_index , - 1 ): if right_max < height [ i ]: right_max = height [ i ] total_water += right_max - height [ i ] return total_water

```

### CPP

```cpp
// OJ: https://leetcode.com/problems/trapping-rain-water/ // Time: O(N) // Space: O(N) class Solution { public: int trap ( vector < int >& A ) { int N = A . size (), ans = 0 ; vector < int > left ( N , 0 ), right ( N , 0 ); for ( int i = 1 ; i < N ; ++ i ) left [ i ] = max ( left [ i - 1 ], A [ i - 1 ]); for ( int i = N - 2 ; i >= 0 ; -- i ) right [ i ] = max ( right [ i + 1 ], A [ i + 1 ]); for ( int i = 1 ; i < N - 1 ; ++ i ) ans += max ( 0 , min ( left [ i ], right [ i ]) - A [ i ]); return ans ; } };
```