Trapping Rain Water
Post
Cancel

# LeetCode #42: Trapping Rain Water (C/C++).

hard

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 * 104
• 0 <= height[i] <= 105

## Solution

To be able to trap water at the ith 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 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; } };