42. Trapping Rain Water

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

Description: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Solution:

Core Idea: You are walking between walls of different heights (the array of numbers). Your goal is to calculate how much rainwater could be trapped between these walls after it rains. The amount of water that can be trapped above a section of wall is determined by the height of the shorter walls on either side of that section.

Why Two Pointers?

• Left and Right Pointers: These pointers start at the beginning and end of the array, respectively. They represent walls. We move them towards each other as we calculate the trapped water.
• LeftMax and RightMax Variables: They represent the tallest walls encountered so far as you move the left and right pointers. They are crucial because the ability of a wall to trap water is determined not by the walls immediately next to it, but by the tallest walls to its left and right.

Simplified Steps:

1. Initialization: Set left to 0 (start of the array) and right to the last index of the array. Also, initialize leftMax and rightMax to 0. These will track the tallest walls we've seen so far from both directions.

2. Loop until the pointers meet: Repeat the following steps until left is less than right. Each step represents moving through the array from both ends towards the middle.

3. Compare left and right walls:

• If the wall at the left pointer is lower than the wall at the right pointer, it means the left side is the limiting factor (since water height is determined by the shorter of the two sides). Therefore, we check if we can trap water on the left.
• If height[left] is greater than leftMax, update leftMax to height[left] because we've found a new tallest wall on the left side.
• If height[left] is less than or equal to leftMax, it means this wall is in a 'valley', and we can trap leftMax - height[left] units of water above this wall. Move the left pointer to the right (increment).
• Otherwise, the logic is mirrored for the right side with rightMax.

4. Incrementing/Decrementing Pointers: Depending on the comparison, move either left or right pointer:

• If we just processed the left side, increment left to move right.
• If we processed the right side, decrement right to move left.

5. Continue until pointers meet: Keep looping and calculating trapped water until left and right meet. This ensures we've checked every section of the wall array.

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let left = 0
  let right = height.length - 1
  let leftMax = 0
  let rightMax = 0
  let totalWater = 0

  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] >= leftMax) {
        leftMax = height[left]
      } else {
        totalWater += leftMax - height[left]
      }
      left++
    } else {
      if (height[right] >= rightMax) {
        rightMax = height[right]
      } else {
        totalWater += rightMax - height[right]
      }
      right--
    }
  }

  return totalWater
}

Takeaway:

The Two Pointers Approach smartly navigates the array from both ends, constantly updating the maximum heights encountered and calculating the trapped water based on the shorter side's height at each step, thereby efficiently solving the problem with a single pass through the array.