📅 Date: Feb 9, 2026
🔥 Topic: Hard Algorithm: Trapping Rainwater

🌧️ The 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.

🧠 The Logic: Min(MaxL, MaxR) - Height

Water stored on top of any block depends on:
1. The tallest building to its Left.
2. The tallest building to its Right.
Formula: Water = min(LeftMax, RightMax) - CurrentHeight

📊 Dry Run Table

Array: [4, 2, 0, 3, 2, 5]

Index Height Left Max (So far) Right Max (From end) Calculation (Min(L,R) - H) Water Trapped
0 4 4 5 4 - 4 0
1 2 4 5 4 - 2 2
2 0 4 5 4 - 0 4
3 3 4 5 4 - 3 1
4 2 4 5 4 - 2 2
5 5 5 5 5 - 5 0

Total Water: 0 + 2 + 4 + 1 + 2 + 0 = 9 Units

💻 Day 39 Code (Optimized)

#include <iostream>
#include <vector>
#include <algorithm> // for max/min
using namespace std;

int trap(vector<int>& height) {
    int n = height.size();
    
    // Auxiliary Arrays
    vector<int> leftMax(n), rightMax(n);

    // Fill Left Max
    leftMax[0] = height[0];
    for(int i=1; i<n; i++) 
        leftMax[i] = max(height[i], leftMax[i-1]);

    // Fill Right Max
    rightMax[n-1] = height[n-1];
    for(int i=n-2; i>=0; i--) 
        rightMax[i] = max(height[i], rightMax[i+1]);

    int water = 0;
    for(int i=0; i<n; i++) {
        water += min(leftMax[i], rightMax[i]) - height[i];
    }
    
    return water;
}

int main() {
    vector<int> heights = {4, 2, 0, 3, 2, 5};
    cout << "Trapped Water: " << trap(heights) << endl;
    return 0;
}

💭 Thoughts

This problem felt impossible at first, but breaking it down into "Left Support" and "Right Support" made it logical. This is a standard Hard problem, and I just solved it!