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.

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;
  }
};