Trapping Rain Water Ii - Leetcode Solution

Problem:

Given an array of integers representing heights of blocks where the width of each block is 1, compute how much water can be trapped after raining.

Example:

Input: [4,2,0,3,2,5] Output: 9

Explanation: In this example, the heights of the blocks are [4,2,0,3,2,5]. If it rains, 9 units of water (marked in blue) can be trapped.

Solution:

To solve this problem, we can use a stack to keep track of the indices of the blocks that form a valley. We start off by iterating through the entire array and for each block, we check if it is higher than the last block in the stack. If it is, we pop the stack until we find a block that is higher than the current block or the stack is empty. For each popped block, we calculate the amount of water that can be trapped between it and the current block and add it to our total. Finally, we push the current block index onto the stack.

Here is the implementation of the above algorithm:

def trap(height):
    stack = []
    trapped_water = 0

    for i in range(len(height)):
        while stack and height[i] > height[stack[-1]]:
            bottom_index = stack.pop()
            if not stack:
                break
            width = i - stack[-1] - 1
            depth = min(height[i], height[stack[-1]]) - height[bottom_index]
            trapped_water += width * depth
        stack.append(i)

    return trapped_water

Let’s break it down into steps:

1. We initialize an empty stack and a variable to keep track of the trapped water.
2. We iterate through the entire array using a for loop.
3. For each block, we check if it is higher than the last block in the stack. If it is, we pop the stack until we find a block that is higher than the current block or the stack is empty.
4. For each popped block, we calculate the amount of water that can be trapped between it and the current block and add it to our total.
5. Finally, we push the current block index onto the stack.
6. We return the total amount of trapped water.

This algorithm has a time complexity of O(n) and a space complexity of O(n), where n is the length of the input array.

Overall, this problem is a good application of stack data structure and can be solved easily using it.

1