Rain Terraces (Trapping Rain Water) Problem
Algorithm · Core
Step through it: Monotonic Stack pattern
Step 1 of 7
Goal: for each number, find the next bigger number to its right. Comparing every number with everything after it is slow. Instead keep a stack of numbers that are still waiting for a bigger one.
Step 2 of 7
Take 2. Nothing to compare yet, so it waits on the stack.
Step 3 of 7
Take 1. It is smaller than the waiting 2, so it cannot be anyone's answer. It waits too, on top.
Step 4 of 7
Take 5. It is bigger than 1, so 5 is the answer for 1. Pop 1. It is bigger than 2 as well, so pop 2 too. Then 5 waits.
Step 5 of 7
Take 3. Smaller than 5, so it waits on top.
Step 6 of 7
Take 6. It beats 3 and 5, so both get answer 6. Whatever is left never found a bigger number. Each number is pushed once and popped once, so it is one pass. The stack stays in decreasing order, which is why this is called a monotonic stack.
Step 7 of 7
Your turn.
Given an array of non-negative integers representing terraces in an elevation map
where the width of each bar is 1, compute how much water it is able to trap
after raining.
Examples
Example #1
Input: arr[] = [2, 0, 2]
Output: 2
Structure is like below:
| |
|_|
We can trap 2 units of water in the middle gap.Example #2
Input: arr[] = [3, 0, 0, 2, 0, 4]
Output: 10
Structure is like below:
|
| |
| | |
|__|_|
We can trap "3*2 units" of water between 3 an 2,
"1 unit" on top of bar 2 and "3 units" between 2
and 4. See below diagram also.Example #3
Input: arr[] = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6
Structure is like below:
|
| || |
_|_||_||||||
Trap "1 unit" between first 1 and 2, "4 units" between
first 2 and 3 and "1 unit" between second last 1 and last 2.The Algorithm
An element of array can store water if there are higher bars on left and right.
We can find amount of water to be stored in every element by finding the heights
of bars on left and right sides. The idea is to compute amount of water that can
be stored in every element of array. For example, consider the array
[3, 0, 0, 2, 0, 4], We can trap "3*2 units" of water between 3 an 2, "1 unit"
on top of bar 2 and "3 units" between 2 and 4. See below diagram also.
Approach 1: Brute force
Intuition
For each element in the array, we find the maximum level of water it can trap after the rain, which is equal to the minimum of maximum height of bars on both the sides minus its own height.
Steps
- Initialize
answer = 0 - Iterate the array from left to right:
- Initialize
max_left = 0andmax_right = 0 - Iterate from the current element to the beginning of array updating:
max_left = max(max_left, height[j]) - Iterate from the current element to the end of array updating:
max_right = max(max_right, height[j]) - Add
min(max_left, max_right) − height[i]toanswer
- Initialize
Complexity Analysis
Time complexity: O(n^2). For each element of array, we iterate the left and right parts.
Auxiliary space complexity: O(1) extra space.
Approach 2: Dynamic Programming
Intuition
In brute force, we iterate over the left and right parts again and again just to find the highest bar size up to that index. But, this could be stored. Voila, dynamic programming.
So we may pre-compute highest bar on left and right of every bar in O(n) time.
Then use these pre-computed values to find the amount of water in every array element.
The concept is illustrated as shown:
Steps
- Find maximum height of bar from the left end up to an index
iin the arrayleft_max. - Find maximum height of bar from the right end up to an index
iin the arrayright_max. - Iterate over the
heightarray and updateanswer:- Add
min(max_left[i], max_right[i]) − height[i]toanswer.
- Add
Complexity Analysis
Time complexity: O(n). We store the maximum heights upto a point using 2
iterations of O(n) each. We finally update answer using the stored
values in O(n).
Auxiliary space complexity: O(n) extra space. Additional space
for left_max and right_max arrays than in Approach 1.
Code
/**
* BRUTE FORCE approach of solving Trapping Rain Water problem.
*
* @param {number[]} terraces
* @return {number}
*/
export default function bfRainTerraces(terraces) {
let waterAmount = 0;
for (let terraceIndex = 0; terraceIndex < terraces.length; terraceIndex += 1) {
// Get left most high terrace.
let leftHighestLevel = 0;
for (let leftIndex = terraceIndex - 1; leftIndex >= 0; leftIndex -= 1) {
leftHighestLevel = Math.max(leftHighestLevel, terraces[leftIndex]);
}
// Get right most high terrace.
let rightHighestLevel = 0;
for (let rightIndex = terraceIndex + 1; rightIndex < terraces.length; rightIndex += 1) {
rightHighestLevel = Math.max(rightHighestLevel, terraces[rightIndex]);
}
// Add current terrace water amount.
const terraceBoundaryLevel = Math.min(leftHighestLevel, rightHighestLevel);
if (terraceBoundaryLevel > terraces[terraceIndex]) {
// Terrace will be able to store the water if the lowest of two left and right highest
// terraces are still higher than the current one.
waterAmount += terraceBoundaryLevel - terraces[terraceIndex];
}
}
return waterAmount;
}/**
* DYNAMIC PROGRAMMING approach of solving Trapping Rain Water problem.
*
* @param {number[]} terraces
* @return {number}
*/
export default function dpRainTerraces(terraces) {
let waterAmount = 0;
// Init arrays that will keep the list of left and right maximum levels for specific positions.
const leftMaxLevels = new Array(terraces.length).fill(0);
const rightMaxLevels = new Array(terraces.length).fill(0);
// Calculate the highest terrace level from the LEFT relative to the current terrace.
[leftMaxLevels[0]] = terraces;
for (let terraceIndex = 1; terraceIndex < terraces.length; terraceIndex += 1) {
leftMaxLevels[terraceIndex] = Math.max(
terraces[terraceIndex],
leftMaxLevels[terraceIndex - 1],
);
}
// Calculate the highest terrace level from the RIGHT relative to the current terrace.
rightMaxLevels[terraces.length - 1] = terraces[terraces.length - 1];
for (let terraceIndex = terraces.length - 2; terraceIndex >= 0; terraceIndex -= 1) {
rightMaxLevels[terraceIndex] = Math.max(
terraces[terraceIndex],
rightMaxLevels[terraceIndex + 1],
);
}
// Not let's go through all terraces one by one and calculate how much water
// each terrace may accumulate based on previously calculated values.
for (let terraceIndex = 0; terraceIndex < terraces.length; terraceIndex += 1) {
// Pick the lowest from the left/right highest terraces.
const currentTerraceBoundary = Math.min(
leftMaxLevels[terraceIndex],
rightMaxLevels[terraceIndex],
);
if (currentTerraceBoundary > terraces[terraceIndex]) {
waterAmount += currentTerraceBoundary - terraces[terraceIndex];
}
}
return waterAmount;
}References
Practice
Monotonic Stack
- Valid ParenthesesEasy
- Next Greater Element IEasy
- Min StackEasy
- Baseball GameEasy
- Remove All Adjacent Duplicates In StringEasy
- Daily TemperaturesMedium
- Next Greater Element IIMedium
- Evaluate Reverse Polish NotationMedium
- Decode StringMedium
- Remove K DigitsMedium
- Online Stock SpanMedium
- Car FleetMedium
- Asteroid CollisionMedium
- Simplify PathMedium
- 132 PatternMedium
- Sum of Subarray MinimumsMedium
- Largest Rectangle in HistogramHard
- Maximal RectangleHard
- Trapping Rain WaterHard
- Basic CalculatorHard
Spotted a mistake or something unclear? Report it on GitHub.