Problems this week are about stack although it’s not so obvious.
The Similarity between two problems is that when traversing the array at some point, some “states” right before that point would not affect the ultimate result anymore, so they can be reduced (pop out of the stack) and leaving those that will still probably affect the result.
Although the idea seems to be very simple, but it still take me a lot of times to come up with. And here are two problems.
42. Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
My accepted code can be found here
Obviously we need to do linear scan over the input array. The problem is how to calculate the total collected water during the scan. The observation is that a taller wall would block all shorter walls before it (in terms of the order of scan).
So we maintain all the walls in a stack during the scan, whenever a wall appears, we can dump all the shorter walls from the top of the stack, and calculate the water collection during the process, until the top of the stack is a taller wall, then the wall is pushed.
And it turns out that the calculation of volumn of collected water is fairly simple. So here’s the algorithm.
RainWater(heights: int[]):
let stk = empty stack of integer pair
let water = 0
for i = 0 to length(heights):
let p = (i, heights[i])
if isEmpty(stk) then stk.push(p)
else water = water + Reduce(stk, p)
stk.push(p)
return water
Reduce(stk: stack, p: (int, int)):
let water = 0
let collected = 0
for not isEmpty(stk) and stk.top[1] <= p[1]:
water += (skt.top[1] - collected) * (p[0] - skt.top[0] - 1)
collected = skt.top[1]
stk.pop()
if not stk.empty()
then water += (p[1] - collected) * (i - stk.top[0])
return water
The idea is that when reducing stack, we calculate the water from button to top. The time complexity of the algorithm is O(n) because all walls is pushed and popped at most once.
84. Largest Rectangle in Histogram
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
For example, Given heights = [2,1,5,6,2,3], return 10.
My accepted code can be found here
This problem is relatively harder than the problem before. The most difficult part is how do we calculate the current maximum area in an efficient way and keep all the information we need in the future at the same time.
Here the basic observation is that, the shorter rectangle “block” all the taller rectangles before it. All rectangles after it cannot make use of the taller parts to form a larger rectangle.
So if we use stack again, the condition to reduce the stack is clear. But how to calculate the maximum area during the stack operation? What information should we store in the stack alone with the height of rectangles?
Because the stack reduce process remove all rectangles that is taller than the current rectangle, in the future we may need to calculate the area behind the rectangle. So each time we reduce rectangles, we need to count how many rectangles are reduced, for example the stack is [1, 3, 4], can current height is 2. After the reduction we have stack [1, 2]. So we should be able to tell the ‘2’ here actually represents three block, so the 2 alone has an area of 6. And that’s all we need in future calculation.
The rest problems lies in what happens if taller rectangle comes. How do we calculate this part of area (Just as the case in the example). Observing that if “tall” rectangles are seperated by “short” rectangles into different parts, we could calculate the area of them seperately, my solution is calculate them in reduction is enough. So here’s the algorithm.
RectangleArea(heights: int[]):
let result = 0
let stk = empty stack of integer pair
for i = 0 to length(heights):
if isEmpty(stk) or heights[i] > stk.top[0]
then stk.push((heights[i], 1))
else result = max(result, reduce(stk, heights[i]))
result = max(result, reduce(stk, 0))
return result
Reduce(stk: stack, height: int):
let result = 0
let count = 0
for not isEmpty(stk) and height <= stk.top()[0]:
count += stk.top[1]
result = max(result, stk.top[0] * count)
stk.pop()
stk.push((height, count + 1))
reutrn result
When we are reducing the stack, since the height in stack is guaranteed in an ascending order, so the rectangle close to bottom can form a rectangle in its own height with all rectangles above, so we can do stk.top[0] * count. And we accumulate the maximum area during the process. And do a one last reduction of stack when input runs out.
The time complexity is again O(n) since every rectangle is pushed and popped at most once.
Conclusion
This time the “pseudo code” are more detailed since I cannot express the whole algorithm in a more concise way like dynamic programming or searching algorithm.
Stack seems to be a very simple data structure but the application of it can vary a lot. The two problems today for example, at first glance I didn’t even realize they were stack problems. They are both very interesting problems.