Trapping Rain Water hard

Problem Statement

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

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map 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

Steps and Explanation

The core idea is to find, for each bar, how much water it can trap. This depends on the maximum height to its left and the maximum height to its right. The water trapped above a bar is the minimum of the left and right maximums, minus the bar's height. We iterate through the array, calculating this trapped water for each bar and summing it up.

We can optimize this by using two arrays, left_max and right_max, to pre-compute the maximum heights to the left and right of each bar, respectively. This avoids redundant calculations during the main iteration.

1. Initialization: Create two arrays, left_max and right_max, of the same size as height.
2. Left Max Calculation: Iterate through height from left to right. For each index i, left_max[i] will store the maximum height encountered so far.
3. Right Max Calculation: Iterate through height from right to left. For each index i, right_max[i] will store the maximum height encountered so far.
4. Water Trapping Calculation: Iterate through height. For each index i, calculate the trapped water as min(left_max[i], right_max[i]) - height[i]. Sum up these values to get the total trapped water.

Code

#include <vector>
#include <algorithm>

using namespace std;

int trap(vector<int>& height) {
    int n = height.size();
    if (n == 0) return 0;

    vector<int> left_max(n);
    vector<int> right_max(n);

    left_max[0] = height[0];
    for (int i = 1; i < n; ++i) {
        left_max[i] = max(height[i], left_max[i - 1]);
    }

    right_max[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        right_max[i] = max(height[i], right_max[i + 1]);
    }

    int trapped_water = 0;
    for (int i = 0; i < n; ++i) {
        trapped_water += max(0, min(left_max[i], right_max[i]) - height[i]);
    }

    return trapped_water;
}

Complexity

• Time Complexity: O(n), where n is the number of bars in the elevation map. We iterate through the array three times: once for left_max, once for right_max, and once for calculating trapped water.
• Space Complexity: O(n), due to the use of left_max and right_max arrays. We could potentially reduce this to O(1) using two pointers, but the code would be slightly more complex.