Trapping Rain Water (using Stack) 🌧️🏠

Welcome to this enlightening journey on Data Structures and Algorithms! Today, we'll dive into a fascinating problem called "Trapping Rain Water" using the mighty Stack 📦!

This lesson is designed for both beginners and intermediate learners. By the end of it, you'll understand the problem's intricacies and how to implement it using a Stack. Let's embark on this learning adventure together! 🎯

Understanding the Problem 💡

Imagine you have a collection of buildings, each with a roof representing a container to trap rainwater. The width and height of each building can vary. Now, let's consider it has rained, and the water is accumulating on these rooftops. The goal is to find the maximum amount of water that can be trapped in the containers.

Here's a simple example:

Buildings: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

  ^
  |
  |
  |  Water level
  |
  v
[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

In this example, we can trap 6 units of water between the buildings with heights 2 and 3.

Implementing the Solution 📝

To solve this problem, we'll use a Stack to keep track of the highest building on the right side of the current position. This allows us to calculate the water that can be trapped in each container.

Here's a step-by-step breakdown of the algorithm:

Initialize an empty Stack and an accumulator variable to store the total trapped water.
Iterate through the array of building heights. For each building, perform the following steps:

a. Push the current building height onto the Stack if it's the first building or the current height is higher than the top of the Stack.

b. If the current building height is lower than the top of the Stack, calculate the water level and add it to the total trapped water. Then, pop the top of the Stack.
After iterating through the array, calculate the water level between the last building and the top of the Stack if there's any water left in the Stack.

Code Example ✅

Now, let's write the code in JavaScript!

javascript

function trapRainWater(heights) {
  if (heights.length <= 1) return 0;

  const stack = [];
  let totalWater = 0;

  for (let i = 0; i < heights.length; i++) {
    // Push the current building height onto the Stack if it's the first building or the current height is higher than the top of the Stack.
    while (stack.length > 0 && heights[stack[stack.length - 1]] < heights[i]) {
      const left = stack.pop();

      // If the current building height is lower than the top of the Stack, calculate the water level and add it to the total trapped water.
      if (stack.length > 0) {
        const distance = i - stack[stack.length - 1] - 1;
        totalWater += distance * (Math.min(heights[left], heights[i]) - heights[left]);
      } else {
        totalWater += (i - stack[stack.length - 1]) * (heights[i]);
      }
    }

    // Push the current building height onto the Stack.
    stack.push(i);
  }

  // Calculate the water level between the last building and the top of the Stack if there's any water left in the Stack.
  if (stack.length > 0) {
    const right = heights.length - 1;
    totalWater += stack[stack.length - 1] - 1;
  }

  return totalWater;
}

const buildings = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
console.log(trapRainWater(buildings)); // Output: 6

Practice Time 📝

Now, let's test your understanding with a few quiz questions!

That's all for today! I hope you enjoyed this deep dive into the "Trapping Rain Water" problem using a Stack. Stay tuned for more Data Structures and Algorithms lessons! 🌧️🏠

If you found this lesson helpful, feel free to share it with your fellow learners! 🤝

Happy coding! 💻💡