DSA / 5 min read
Day 8 of 60 Days DSA — Rain Water Trapped
Uncovering Water Pockets Between Bars Using Efficient Techniques
Day 8 of 60 Days DSA — Rain Water Trapped
Uncovering Water Pockets Between Bars Using Efficient Techniques
Welcome to Day 8 of 60 Days DSA! Today, we’re exploring one of the classic histogram-based array problems that often shows up in coding interviews and leaves candidates blank.
Trapping Rain Water. This problem asks you to determine how much rainwater can be collected between vertical bars of differing heights — a task that forces you to think in terms of boundaries and optimisations.
Problem Statement:
Imagine a histogram where the bars’ heights are given by the array A. Each bar is of uniform width, which is 1 unit. When it rains, water will accumulate in the valleys between the bars.
Your task is to calculate the total amount of water that can be trapped in these valleys.
Example Input
Input 1:
A = [0, 1, 0, 2]
Input 2:
A = [1, 2]
Example Output
Output 1:
1
Output 2:
0
Example Explanation
Explanation 1:
Explanation 2:
No water is trapped.
Intuition
The water can only be trapped over a bar if the bar to its left and right has a greater heights the current bar.
Now the question is how much water can be stored??
If you look at the image, it is clear that the Water trapped on top of a bar depends on the tallest bar to its left and the tallest bar to its right. The limiting factor is the shorter of these two: water cannot accumulate higher than the shortest boundary. So we can derive a formula like this. If you have any confusion in understanding this, please comment below.
water_at_i = min(max_left[i], max_right[i]) - height[i]Now we understand what we need to do, so let's code it out.
Brute Force Approach
1. Brute Force (O(n²))
For every bar:
- Find the maximum height to its left — O(n)
- Find the maximum height to its right — O(n)
- Subtract the bar’s height from the smaller of the two.
For doing each of the steps for each bar, it’ll be O(n*n)
Simple, but inefficient for large arrays.
2. Optimised Approach using Stack
This solution first precomputes the left and right boundaries for every bar using a monotonic decreasing stack.
For each index, the stack helps find the nearest taller bar on the left and on the right in O(n) time.
Once these boundaries are known, the trapped water at index i is calculated as:
min(leftMax[i], rightMax[i]) − height[i]Summing this for all indices gives the total trapped water.
Code For Stack Approach
// Main function
function rainWaterTrapped(A){
left = findLeftMax(A);
right = findRightMax(A);
let totalWaterTrapped = 0;
for(let i=0; i< A.length; i++){
let min = Math.min(left[i], right[i]);
totalWaterTrapped += min > 0 ? min- A[i] : 0;
}
return totalWaterTrapped;
}
// function to calculate left max bar to each of the bar
function findLeftMax(A){
let arr = [], stack = [];
for(let i =0; i< A.length; i++){
while(stack.length != 0 && top(stack) < A[i]){
stack.pop();
}
if(stack.length == 0){
arr[i] = -1;
stack.push(A[i]);
}else{
arr[i] = top(stack);
}
}
return arr;
}
// function to calculate right max bar to each of the bar
function findRightMax(A){
let arr =[], stack = [];
for(let i = A.length-1; i>=0; i--){
while(stack.length != 0 && top(stack) < A[i]){
stack.pop()
}
if(stack.length == 0){
arr[i] = -1;
stack.push(A[i]);
}else{
arr[i] = top(stack);
}
}
return arr;
}
// helper function
function top(stack){
let n = stack.length;
return n > 0 ? stack[n-1] : null;
}Complexity
Time complexity
findLeftMax — O(n)
findRightMax- O(n)
Final traversal- O(n)
Overall — O(n)
Space Complexity
findLeftMax — O(n)
findRightMax- O(n)
Final traversal- O(1)
Overall — O(n)
Wrap-Up
The Trapping Rain Water problem helps build a strong understanding of array boundaries and optimisation techniques. By recognising that trapped water depends on the nearest taller bars on both sides, we can move from an inefficient brute-force solution to an optimal monotonic stack approach.
With this, you’ve completed Day 8 of 60 Days DSA — another step closer to thinking in optimised problem-solving patterns.
Do you want to solve more with us?
Then follow this series and share your progress in the comments.
If the topics are difficult for you to understand, then you can refer to the notes on my GitHub.
At Dev Simplified, We Value Your Feedback 📊
👉 Follow us to not miss any updates.
👉 Have any suggestions? Let us know in the comments!