42. Trapping Rain Water 🔥

Hard

Problem:

Given a height, calculate how much water can accumulate after it rains.

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] 
Output: 6 
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

https://leetcode.com/problems/trapping-rain-water/

Solutions:

What role does that bar play? It plays an important role for being the highest, but it actually wouldn't matter if that bar instead had height 100. It wouldn't affect the volume.

The tallest bar forms a barrier for water on its left and right. But the volume of water is actually controlled by the next highest bar on the left and right.

Reference: Gayle Laakmann Mcdowell, Cracking the Coding Interview 6th edition, p608

Two Pointers

The left and right pointers meet at the highest bar - the 'maximum' point, and the problem can be solved in $O(n)$.

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        volume = 0
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]

        while left < right:
            left_max, right_max = max(height[left], left_max), max(height[right], right_max)
            if left_max <= right_max:
                volume += left_max - height[left]
                left += 1
            else:
                volume += right_max - height[right]
                right -= 1
        return volume

Know more about Two Pointers? Click the page below ⬇️

5. Longest Palindromic Substring 🔥

Stack

It is quite hard to intuitively come up with this solution.

Keep stacking on the stack, and when the current height is higher than the previous one, i.e., whenever you meet an inflection point, pull one out of the stack and fill the water height by the difference with the previous one.

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        volume = 0
        
        for i in range(len(height)):
            # Meet inflection point
            while stack and height[i] > height[stack[-1]]:
                top = stack.pop()
                
                if not len(stack):
                    break
                
                # Different height from previous one
                distance = i - stack[-1] -1
                waters = min(height[i], height[stack[-1]]) - height[top]
                
                volume += distance * waters
            
            stack.append(i)
        return volume

Why do we need to check len(stack) in while statement?

In the provided code, the stack is used to keep track of the indices of the bars in the histogram. It's done in such a way that the heights of the bars are in non-increasing order from the bottom to the top of the stack.

In the inner while loop, we pop elements (indices of bars) from the stack until we find a bar on the stack which is higher than the current one. The popped bar is considered the bottom of a container.

However, after popping the bottom bar, we need a left boundary of the container. The left boundary is the current top element of the stack. But if the stack is empty (which can happen if all previously met bars are lower than the current one), there's no left boundary and we can't form a container to hold any water. Therefore, we need to break the loop.

In summary, the check if not len(stack): is there to prevent a situation where we are trying to form a container without a left boundary. Without this check, the code would raise an error when trying to access stack[-1] when stack is empty.