Trapping Rain Water — Solution

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

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

0 <= n <= 3 * 104

0 <= height[i] <= 105

Solution —

#include <bits/stdc++.h>
using namespace std;
int RainWaterTrapping(int * arr, int n) {
 int maxLeft[n];
 int maxRight[n];
maxLeft[0] = arr[0];
 maxRight[n — 1] = arr[n — 1];
for (int i = 1; i < n; i++)
 maxLeft[i] = max(maxLeft[i — 1], arr[i]);
for (int i = n — 2; i >= 0; i — )
 maxRight[i] = max(maxRight[i + 1], arr[i]);
vector < int > water;
int sum = 0;
for (int i = 0; i < n; i++) {
 water.push_back(min(maxLeft[i], maxRight[i]) — arr[i]);
 sum += water[i];
 }
return sum;
}
int main() {
 int n;
 cin >> n;
 int arr[n];
for (int i = 0; i < n; i++)
 cin >> arr[i];
cout << RainWaterTrapping(arr, n);
 return 0;
}