hard

Trapping Rain Water

To solve the problem of trapping rainwater on an elevation map, we can use a two-pointer approach. The idea is to maintain two pointers, one starting from the left and another from the right. We iterate through the array, comparing the heights at the left and right pointers. Based on the comparison, we update the pointers and calculate the trapped water at each position.

Here's implementation of the algorithm:

function trapRainwater(heights) {
  let left = 0;
  let right = heights.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let waterTrapped = 0;
 
  while (left < right) {
    if (heights[left] < heights[right]) {
      if (heights[left] >= leftMax) {
        leftMax = heights[left];
      } else {
        waterTrapped += leftMax - heights[left];
      }
      left++;
    } else {
      if (heights[right] >= rightMax) {
        rightMax = heights[right];
      } else {
        waterTrapped += rightMax - heights[right];
      }
      right--;
    }
  }
 
  return waterTrapped;
}

In this solution, we initialize the left pointer at the beginning of the array (index 0) and the right pointer at the end of the array (index heights.length - 1). We also initialize variables leftMax and rightMax to keep track of the maximum height encountered from the left and right sides, respectively. The waterTrapped variable is used to accumulate the total trapped water.

We then enter a loop where we compare the heights at the left and right pointers. If the height at the left pointer is less than the height at the right pointer, we update the leftMax if necessary and calculate the trapped water using the difference between leftMax and the height at the left pointer. We then move the left pointer to the right.

If the height at the right pointer is less than or equal to the height at the left pointer, we follow a similar process but update the rightMax instead.

The loop continues until the left pointer is equal to the right pointer, indicating that we have iterated through the entire array.

The time complexity of this algorithm is O(n), where n is the length of the input array heights. We iterate through the array once using the two-pointer approach.

The space complexity is O(1) because we use a constant amount of extra space regardless of the input size.