Problem Statement

Given an array height[] where each element represents the height of a building, find the total amount of rainwater that can be trapped after raining.

Example

Input:

height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output:

6

Brute Force Intuition (Interview Explanation)

For every building, find the tallest building on its left and the tallest building on its right.

The amount of water stored at the current index depends on the smaller of these two boundaries because water cannot exceed the shorter wall.

Water stored at index i:

min(leftMax, rightMax) - height[i]

We repeat this process for every index and accumulate the answer.

Time Complexity

O(N²)

Space Complexity

O(1)

Brute Force Java

class Solution {
 public int trap(int[] height) {
 int n = height.length;
 int water = 0;

 for (int i = 0; i < n; i++) {

 int leftMax = 0;
 int rightMax = 0;

 for (int j = 0; j <= i; j++) {
 leftMax = Math.max(leftMax, height[j]);
 }

 for (int j = i; j < n; j++) {
 rightMax = Math.max(rightMax, height[j]);
 }

 water += Math.min(leftMax, rightMax) - height[i];
 }

 return water;
 }
}

Moving Towards Optimal

In the brute force approach, we repeatedly calculate the left maximum and right maximum for every index.

Instead, we can precompute:

• leftMax[i] = maximum height from 0 to i
• rightMax[i] = maximum height from i to n-1

Now, for every index, the trapped water can be calculated in constant time.

This removes repeated scans and reduces the complexity from O(N²) to O(N).

Optimal Approach – Prefix Max & Suffix Max

Algorithm

1. Build the leftMax array.
2. Build the rightMax array.
3. For every index:

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

1. Return total water.

Why It Works

Water can only stay if there is a boundary on both sides.

The maximum possible water level at any position is determined by the smaller boundary among the tallest wall on the left and the tallest wall on the right.

Therefore:

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

Optimal Java Solution

class Solution {
 public int trap(int[] height) {

 int n = height.length;
 if (n == 0) return 0;

 int[] leftMax = new int[n];
 int[] rightMax = new int[n];

 leftMax[0] = height[0];
 rightMax[n - 1] = height[n - 1];

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

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

 int trappedWater = 0;

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

 return trappedWater;
 }
}

Dry Run

Input:

height = [4,2,0,3,2,5]

Left Max:

[4,4,4,4,4,5]

Right Max:

[5,5,5,5,5,5]

Total Water:

0 + 2 + 4 + 1 + 2 + 0 = 9

Pattern Recognition

This pattern appears whenever a problem asks for:

• Left and right boundaries
• Maximum constraint from both directions
• Contribution of each index based on surrounding elements
• Water trapping between bars

Common tools:

• Prefix Maximum Array
• Suffix Maximum Array
• Two Pointer Optimization

Interview One-Liner

For every index, the water level is determined by the smaller of the tallest building on its left and right. By precomputing these boundaries using prefix and suffix maximum arrays, we can calculate trapped water for every position in O(N) time and O(N) space.