Hey readers! 👋

Today we’re diving into a classic yet mind-bending coding interview problem that’s not just interesting but teaches you a lot about problem-solving with arrays.

Let’s talk about the Trapping Rain Water problem.

🌧️ Problem Statement:

You're given an array height[] of length n.
Each element in this array represents the height of a bar on an elevation map, where each bar has a width of 1 unit.

Your task is to calculate how much water is trapped between the bars after it rains.

Input: [4, 2, 0, 6, 3, 2, 5]
Output:[11]

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

We will go step-by-step through the logic, and then visualize how water is trapped at each index.

🔎 Step 1: Understanding the Terrain

Each number in the array is a bar of height:

Index:   0  1  2  3  4  5  6
Height: [4, 2, 0, 6, 3, 2, 5]

Now, let's find the water trapped at each index.

✅ Step 2: Precompute LeftMax and RightMax

We'll use the left-max and right-max arrays to track the highest bar to the left and right of each position.

▶️ leftMax array:

We go left to right, and at each step:

leftMax[i] = max(height[i], leftMax[i-1])

leftMax[0] = 4
leftMax[1] = max(2, 4) = 4
leftMax[2] = max(0, 4) = 4
leftMax[3] = max(6, 4) = 6
leftMax[4] = max(3, 6) = 6
leftMax[5] = max(2, 6) = 6
leftMax[6] = max(5, 6) = 6

Final leftMax: [4, 4, 4, 6, 6, 6, 6]

▶️ rightMax array:

We go right to left, and at each step:

rightMax[i] = max(height[i], rightMax[i+1])

rightMax[6] = 5
rightMax[5] = max(2, 5) = 5
rightMax[4] = max(3, 5) = 5
rightMax[3] = max(6, 5) = 6
rightMax[2] = max(0, 6) = 6
rightMax[1] = max(2, 6) = 6
rightMax[0] = max(4, 6) = 6

Final rightMax: [6, 6, 6, 6, 5, 5, 5]

💧 Step 3: Water Trapped at Each Index

Now apply the formula:

water[i] = min(leftMax[i], rightMax[i]) - height[i]

📊 Let’s compute:

🧮 Total Water Trapped

Just sum up the last column:

Total = 0 + 2 + 4 + 0 + 2 + 3 + 0 = 11

✅ Answer: 11 units of water trapped

✅ Final Summary
For each index, find the tallest bar on the left and right.

Water trapped = min(leftMax, rightMax) - height.

Total trapped water = sum of trapped water at each index.

Code C++:

int n = height.size();
vector<int> leftMax(n), rightMax(n);

// Step 1: Fill leftMax
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
    leftMax[i] = max(leftMax[i - 1], height[i]);
}

// Step 2: Fill rightMax
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
    rightMax[i] = max(rightMax[i + 1], height[i]);
}

// Step 3: Calculate total trapped water
int trappedWater = 0;
for (int i = 0; i < n; i++) {
    trappedWater += min(leftMax[i], rightMax[i]) - height[i];
}

Code Java:

int n = height.length;
int[] leftMax = new int[n];
int[] rightMax = new int[n];

// Step 1: Fill leftMax
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
    leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}

// Step 2: Fill rightMax
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
    rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}

// Step 3: Calculate trapped water
int trappedWater = 0;
for (int i = 0; i < n; i++) {
    trappedWater += Math.min(leftMax[i], rightMax[i]) - height[i];
}

✅ Time Complexity of Trapping Rainwater (using leftMax[] and rightMax[] arrays):

🔹 Step-by-step Breakdown:

Fill leftMax[] array

Loop runs from 1 to n-1

Time: O(n)

Fill rightMax[] array

Loop runs from n-2 to 0

Time: O(n)

Calculate total trapped water

Loop runs from 0 to n-1

Time: O(n)

✅ Final Time Complexity:

O(n) + O(n) + O(n) = O(n)
So the overall time complexity is: O(n)

🧠 Space Complexity:

leftMax[] = O(n)

rightMax[] = O(n)

Total: O(n)