LeetCode Entry
42. Trapping Rain Water
Trap the water in area between vertical walls
42. Trapping Rain Water hard
blog post
substack
youtube
Problem TLDR
Trap the water in area between vertical walls #hard
Intuition
Let’s observe some examples and try to apply decreasing stack technique somehow:
// #
// # # # #
// # # # # # # # # #
//i0 1 2 3 4 5 6 7 8 91011
// 0 1 0 2 1 0 1 3 2 1 2 1
//0* . 0(0)
//1 * . 1
//2 * . 1(1) 0(2)
//3 * . 2(3) + (3-2)*(1-0)
//4 * . 2(3) 1(4)
//5 * . 2(3) 1(4) 0(5)
//6 * . 2(3) 1(6) + (1-0)*(5-4)
//7 * 3(7) + (2-1)*(6-3)
//2# #
//1## #
//0####
// 0123
//
// 0 1 2 3
// 2 1 0 2
// * 2(0)
// * 2(0) 1(1)
// * 2(0) 1(1) 0(2)
// * 2(3) + a=2,b=1, (i-b-1)*(h[b]-h[a])=(3-1-1)*(1-0)
// a=1,b=0, (3-0-1)*(2-1)
// #
// # #
// # # #
// # # #
// 0 1 2
// 4 2 3
// #
// # #
// # # #
// # # # # #
// # # # # #
// 0 1 2 3 4 5
// 4 2 0 3 2 5
// # #
// # #
// # #
// # # # #
// # # # # # #
// 0 1 2 3 4 5
// 5 2 1 2 1 5
As we meet a new high value we can collect some water. There are corner cases when the left border is smaller than the right.
Approach
- try to come up with as many corner cases as possible
- horizontal width must be between the highest columns
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun trap(height: IntArray): Int = with(Stack<Int>()) {
var sum = 0
for ((i, hb) in height.withIndex()) {
while (size > 0 && height[peek()] <= hb) {
val ha = height[pop()]
if (size > 0) sum += (i - peek() - 1) * (min(hb, height[peek()]) - ha)
}
push(i)
}
return sum
}
pub fn trap(height: Vec<i32>) -> i32 {
let (mut sum, mut stack) = (0, vec![]);
for (i, &hb) in height.iter().enumerate() {
while stack.len() > 0 && height[*stack.last().unwrap()] <= hb {
let ha = height[stack.pop().unwrap()];
if stack.len() > 0 {
let dh = hb.min(height[*stack.last().unwrap()]) - ha;
sum += ((i - *stack.last().unwrap()) as i32 - 1) * dh
}
}
stack.push(i)
}
sum
}