**source:**https://leetcode.com/problems/trapping-rain-water/**C/C++**

**Solution to LeetCode**problem

**42**.

**Trapping Rain Water**.

## 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.

## Examples

**Example 1:**

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 * 10`

^{4}`0 <= height[i] <= 10`

^{5}

## Solution

To be able to trap water at the `i`

position is necessary to have a higher wall to the left and to the right. To be able to do this, we will use the ^{th}**two pointers** technique in order to identify a wall to the left and right.

- We initialize our pointers
`l`

and`r`

to the first ans last position of the array. - At every point, we will keep tracking of what is the
`higher left`

and`higher right`

(`lMax`

and`rMax`

) bars so far “discovered”. - If the
`height[l] <= height[r]`

we will update our`lMax`

or add the amount of water hold at that position to our final result, and move`l`

. - Else, we do the same but for
`r`

and`rMax`

.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
int trap(vector<int>& height) {
int res = 0;
int l = 0;
int r = height.size() - 1;
int lMax = 0;
int rMax = 0;
while (l<=r) {
if (height[l]<=height[r]) {
if (height[l]>=lMax)
lMax = height[l];
else
res += lMax - height[l];
l++;
} else {
if (height[r]>=rMax)
rMax = height[r];
else
res += rMax-height[r];
r--;
}
}
return res;
}
};