Problem Statement

Given an array of integers representing an elevation map where the width of each bar is 1 , return how much rainwater can be trapped .

Steps To Solve

• Verify constraints
  • Do the left and right sides of the graph count as walls ? Ans : No
• Write out some test cases
  • [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] -- 6
  • [ ] -- 0 // Empty Array
  • [3] -- 0 // Array with single value
  • [3,4,3] -- 0 // Water will fall down on edge
• Think of solution without code
  • Looking at 2, 1, 0, 3 area we see that between 2 and 3 , the 2 determines the maximum height the water can go up to .
  • Another important thing to notice is that 1 in 2, 1, 0, 3 ,cuts into how much body of water we have . This tells us not only smaller between the two blocks determines the height of the water but heights on the inside of container also effect how much water is inside .
  • Take 2, 1, 0, 1 for example . The height of water containing at 0 will be min(2 , 1) . The height of water containing at 1 will be min(2,1) - 1 .
  • Lets take another example 5, 2, 1, 0, 1, 4 .Here height of water at 0 will be min(5,4) and height of water at 1 will be min(5,4) - 1 . So from here we got the formula for calculating how much water a single point can contain .
  • currentWater = min(maxLeft , maxRight) - currentHeight .
  • Lets take some variable - total water , - maxLeft , - maxRight .
  • Lets also take a pointer p at the start of Array .
  • Our array is [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] .
  • Using the formula at index 0 and 1 we get values 0 , -1 , 1. If we get -ve values we don't add that to our total .
  • We add all these values to our total and that will be our final result .

const getTrappedRainwater = function (heights) {
  let totalWater = 0;
  for (let i = 0; i < heights.length; i++) {
    let left = i,
      right = i,
      maxLeft = 0,
      maxRight = 0;

    while (left >= 0) {
      maxLeft = Math.max(maxLeft, heights[left]); // Check for max left value iterating towards left.
      left--;
    }

    while (right < heights.length) {
      maxRight = Math.max(maxRight, heights[right]); // Check for max right value iterating towards right.
      right++;
    }

    const currentWater = Math.min(maxLeft, maxRight) - heights[i];

    if(currentWater > = 0)
    {
        totalWater+=currentWater;
    }
  }

  return totalWater;
};

Time and Space Complexity

As we look in our solution for a single pointer we have to iterate through the whole array to find max on both side . For n pointer our time complexity will be O(n^2) which is not optimal . Space complexity in this case is O(1)

Optimizing Solution

In our previous solution, to find the highest bar on the left and right, array traversal is needed which reduces the efficiency of the solution. To make this efficient one must pre-compute the highest bar on the left and right of every bar in linear time. Then use these pre-computed values to find the amount of water in every array element.

So we will iterate through the array once from left and store max values and similarly we do that from the right .

const getTrappedRainwater = function (heights) {
  let left = [];
  let right = [];

  let totalWater = 0;

  left[0] = heights[0];

  for (let i = 1; i < heights.length; i++) {
    left[i] = Math.max(left[i - 1], heights[i]);
  }

  right[heights.length - 1] = heights[heights.length - 1];

  for (let i = heights.length - 2; i >= 0; i--) {
    right[i] = Math.max(right[i + 1], heights[i]);
  }

  for (let i = 0; i < heights.length; i++) {
    totalWater += Math.min(left[i], right[i]) - heights[i];
  }

  return totalWater;
};

Time and Complexity

Time Complexity: O(n) Only one traversal of the array is needed, So time Complexity is O(n).

Space Complexity: O(n) Two extra arrays are needed each of size n.

Optimizing Solution

We reduced the time complexity but in the process of doing so increased the space complexity . A possible optimal solution to reduce space will be to use two pointer techniques . Here instead of using our two pointer to iterate outwards we can try to come inwards with our pointer starting from both the ends.

So if we have two pointers at the extreme end , the only thing we can figure out from this is we have two walls , we cannot anything out about the information on inside of two walls . The water contents can be easily affected by any heights inside of the container .

So one of the pointers must move , either the left one or the right .

What we can see here is that we dont have pointer which was there in our brute force solution . So one of the two pointer must fill its place .

So moving smaller of the two walls makes sense here as it will be the one to impact the amount of water that is stored . Example - [1 ,0 ,2 ] . Water at 0 will be min(2 , 1) - 0 = 1 .

Step By Step Explanation

• Formula currentWater = min(maxLeft , maxRight) - currentHeight
• Lets consider an Array [0 , 1, 0, 2, 1, 0, 3, 1, 0, 1, 2]
• Also we will keep track of flow with some variable maxLeft = 0, maxRight = 0 , currentWater
• Take two pointers p1 and p2 at index-0 and index-10 .
• Now the index-0 can only have water above it if some walls exists on left and has greater values .
• So we move towards right as 0 at index-0 < 2 at index-10 and now p1 is at index-1 .
• As 1 is greater than 0 to left , we update maxLeft = 1 .
• We move to index-2 ,with maxLeft = 1 .
• We see maxLeft > currentHeight , so subtract currentHeight from maxLeft . (1 - 0 = 1) totalWater = 1
• We didn't do min(maxLeft , maxRight) as we know we are moving pointer which has lesser value .
• We move to index-3 . So between index-3 and index-10 we see height of both are equal so we can move anyone of them say we choose left one . We will not do calculation as currentHeight > maxLeft and we will update maxLeft = 2 .
• Moving to index-4 ,we calculate as currentHeight < maxLeft ,result = (2 - 1) = 1 and totalWater = 2 .
• Moving to index-5 ,we calculate as currentHeight < maxLeft ,result = (2 - 0) = 2 and totalWater = 4 .
• Moving to index-6 ,we move towards left from index-10 to index-9 as 2 in index-10 < 3 at index-6 .
• maxRight gets updated to 2 , maxRight = 2
• So we will check between index-6 and index-9 as 1 in index-9 < 3 at index-6 .so will be pick index-9 to move , but before moving lets calculate its value as currentHeight < maxRight ,result = (2 - 1) = 1 and totalWater = 5.
• We move to index-8 ,0 at index-8 < 3 at index-6 , so move to index-7 , but before moving calculate as currentHeight < maxRight , result = (2 - 0) = 2 and totalWater = 7 .
• We are at index-7 ,1 at index-7 < 3 at index-6 ,so move to index-6 , but before moving calculate as currentHeight < maxRight , result = (2 - 1) = 1 and totalWater = 8 .
• Our both pointers are at same position , we break with totalWater = 8 .

Algorithm

• Identify pointers with lesser value
• Is this pointer value lesser than or equal to max on that side
  • Yes - than update max on that side
  • No - get water for pointer value and add to total
• Move pointer inwards
• Repeat for other pointers

const getTrappedRainwater = function (heights) {
  let left = 0,
    right = heights.length - 1,
    leftMax = 0,
    rightMax = 0,
    total = 0;

  while (left < right) {
    if (heights[left] <= heights[right]) {
      if (heights[left] >= leftMax) {
        maxLeft = heights[left];
      } else {
        total += maxLeft - heights[left];
      }

      left++;
    } else {
        if(heights[right] >= rightMax) {
            maxRight = heights[right];
        } else {
            total+ = maxRight - heights[right];
        }

        right--;
  }
  return total;
};

Time and Complexity

Time Complexity: O(n) Only one traversal of the array is needed, So time Complexity is O(n).

Space Complexity: O(1) Two extra arrays are needed each of size n.