Difficulty: Hard, Asked-in: Google, Microsoft, Amazon

Key takeaway: A popular interview problem to learn time and space complexity optimization using various approaches. All the solutions are worth exploring, where the two-pointers approach helps to design an efficient solution in O(n) time and O(1) space.

Let’s understand the problem

Given n non-negative integers representing an elevation map where the width of each tower is 1. Write a program to compute how much water it can trap after raining.

Example 1

Input: height[] = [2, 0, 1, 0, 2], Output: 5

Explanation: Trapped water = 2 x 1 + 1 x 1 + 2 x 1 = 5 (Area of the blue region in the following diagram)

Example 2

Input: height[] = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], Output: 6

Explanation: Trapped water = 1 x 1 + 1 x 1 + 2 x 1 + 1 x 1 + 1 x 1 = 6 (Area of the blue region in the following diagram)

Discussed solution approaches

• A brute force solution using nested loops
• A solution approach using extra memory (Dynamic Programming)
• A solution approach using the stack data structure
• An efficient solution using two pointers approach

A brute force solution  using nested loops

Solution Idea

One basic idea would be to traverse the height[] array and add the water trapped at each tower. The critical question is: how do we find the amount of water trapped by tower height[i]? Let's think!

If we observe closely, the trapped water by tower height[i] will be bounded by the maximum tower height on the left and right sides. The water trapped at height[i] = min (max tower height in the left side, max tower height in the right side) - height[i].

Solution Steps

1. We declare and initialize the variable trappedWater to store the total trapped water.
2. Now we traverse the height[] from from i = 0 to n - 1. Inside the loop, we initialize variables leftMaxHeight and rightMaxHeight to store the maximum height of the tower on the left and right sides of the current tower height[i]. For each height[i]:

3. We run a loop from j = i to 0 and find the maximum height of the tower on the left side. We store this value in the variable leftMaxHeight.

   for(int j = i; j >= 0; j = j - 1)
     leftMaxHeight = max(height[k], leftMaxHeight)
   

4. Similarly, we run a loop from j = i to n - 1 and find the maximum height of the tower on the right side. We store this value in the variable rightMaxHeight.

   for(int j = i; j < n; j = j + 1)
     rightMaxHeight = max(height[j], rightMaxHeight)
   

5. Now using the above formula, we calculate the amount of water trapped by height[i] and add it to the variable trappedWater.

   trappedWater = trappedWater + min(leftMaxHeight, rightMaxHeight) - height[i]
   

6. By end of the above loop, we return the value stored in the variable trappedWater.

Solution Pseudocode

int rain_water_trapping(int height[], int n)
{
    if(n <= 2)
        return 0
    int trappedWater = 0
    for(int i = 0; i < n; i = i + 1)
    {
        int leftMaxHeight = 0 , rightMaxHeight = 0
        
        for(int k = i; k >= 0; k = k - 1)
            leftMaxHeight = max(height[k], leftMaxHeight)
            
        for(int j = i; j < n; j = j + 1)
            rightMaxHeight = max(height[j], rightMaxHeight)
            
        trappedWater = trappedWater 
                       + min(leftMaxHeight, rightMaxHeight) - height[i]
    }
    return trappedWater
}

Solution analysis

• We use two nested loops where the outer loop is scanning the height[] array and two inner loops find rightMaxHeight and leftMaxHeight. So every iteration of the outer loop, we traverse each element of the array using inner loops. So, time complexity = n * O(n) = O(n^2).
• We are using a constant number of variables to get the solution. So, space Complexity = O(1)

A solution approach using extra memory (Dynamic Programming)

Solution Idea

Can we improve the efficiency further and solve the problem in O(n) time? Is it possible to get rid of the inner loops for finding the leftMaxHeight and rightMaxHeight? If the values of leftMaxHeight and rightMaxHeight are known for each tower height[i], we can solve this problem in a single scan of the height[] array. But how can we do this? Let's think!

One idea would be to do some pre-processing to calculate both values for each tower and store them in two separate extra memory of size n. Suppose we take left[n] and right[n] to store the values where left[i] = leftMaxHeight of the tower height[i], right[i] = rightMaxHeight of the tower height[i]. Can we store the values of both arrays in O(n) time? Here is an idea:

• If we know the left[i - 1], then we can easily calculate the left[i] in O(1). Here is the formula: left[i] = max (left[i - 1], height[i]).
• Similarly, if we know right[i + 1], then we can easily calculate the right[i] in O(1). Here is the formula: right[i] = max (right[i + 1], height[i]).
• So, from the above observations, we can store the left[] and right[] array in a single scan of the height[] array. This is a dynamic programming approach where we use the stored solution of the smaller problem to get the solution of the larger problem. Think!

Solution Steps

• We create two arrays left[n] and right[n].

• Now we initialize the left[0] with height[0] and run a loop from i = 1 to n - 1 to store the remaining values in the left[] array. At each iteration i, we store the max element that occurred up to that point in left[i].

  left[0] = height[0]
  for(int i = 1; i < n; i = i + 1)
    left[i] = max(left[i - 1], height[i])
  

• Similarly, we initialize the right[n - 1] with height[n - 1] and run a loop from i = n - 2 to 0 to store the remaining values in the right[] array. At each iteration, we store the max element that occurred up to that point in the right[i].

  right[n - 1] = height[n - 1]
  for(int i = n - 2; i >= 0; i = i - 1)
    right[i] = max(right[i + 1], height[i])
  

• Now, we traverse the height[] array and calculate the total amount of water.

  int trappeWater = 0
  for(int i = 0; i < n; i = i + 1)
    trappedWater = trappedWater + min(left[i], right[i]) - height[i]
  

• Finally, we return the value stored in the variable trappedWater.

Solution Pseudocode

int rain_water_trapping(int height[], int n)
{
    if(n <= 2)
        return 0
    int left[n], right[n]
    left[0] = height[0]
    for(int i = 1; i < n; i = i + 1)
        left[i] = max(left[i-1], height[i])
 
    right[n-1] = height[n-1]
    for(int i = n-2; i >= 0; i = i - 1)
        right[i] = max(right[i+1], height[i])
  
    int trappeWater = 0
    for(int i = 0; i < n; i = i + 1)
        trappedWater = trappedWater + min(left[i], right[i]) - height[i]
        
    return trappedWater
}

Solution Analysis

• In the above pseudocode, we are running three independent loops. So, Time complexity = Time complexity of storing values in left[] array + Time complexity of storing values in right [] array + Time complexity of calcualting the total trapped water = O(n) + O(n) + O(n) = O(n).
• We are using two extra arrays of size n. So space complexity = O(n) + O(n) = O(n)

A solution approach using the stack data structure

Solution Idea

Can we solve this problem in a single scan of the height[] array? Let's explore.

• Area of region 1 = area confined between index 2 and 0
• Area of region 2 = area confined between index 5 and 3
• Area of region 3 = area confined between index 6 and 3
• Area of region 4 = area confined between index 6 and 2
• Area of region 5 = area confined between index 8 and 6
• Area of region 5 = area confined between index 9 and 6

Did we observe some patterns? The idea would be to track the area confined between the current tower and all the previous smaller towers in a sequence. We can use a stack to track the indices of the previous smaller towers. (Think!)

Solution Steps

• We create a stack S to store the indices of the towers.
• Now we traverse the height[] array using a loop: while(i < n).

• If we found a current tower height[i] larger than the tower at the top of the stack, we can say that the tower at the top is confined between the current tower and a previous tower in the stack. Hence, we pop the value from the stack and add water trapped between towers to the total water trapped. We can continue this step in a loop until we find the current tower smaller than the tower at the top of the stack or the stack becomes empty.

  • Water trapped between towers = Area of the rectangular region formed by the current tower, popped tower, and tower at the top of the stack.
  • Region length = current index - index of the top stack element - 1
  • Region height = min (height of the current tower, height of tower at the top of the stack) - the height of the popped tower
  • Water trapped = Region length x Region height
• If the current tower is smaller than or equal to the tower at the top, we push the index of the current tower to the stack and move to the next tower height[i]. It means the current tower is confined with the tower at the top of the stack.
• Finally, we return the value stored in the variable trappedWater.

Solution Pseudocode

int rain_water_trapping(int height[], int n)
{
    int trappeWater = 0, curr = 0
    stack S
    while (curr < n)
    {
        while (!S.empty() && height[curr] > height[S.top()])
        {
            int topTower = S.Pop()
            if (S.empty())
                break
            int regionLength = curr - S.top() - 1
            int regionHeight = min (height[curr], height[S.top()])
                                               - height[topTower]
            trappedWater = trappedWater + regionLength * regionHeight
        }
        S.push(curr)
        curr = curr + 1
    }
    return trappedWater
}

Solution Analysis

We are doing a single traversal of the height[] array. In the worst case, we are processing each tower twice using a stack i.e. one push() and one pop() operation. (Think!) Both push() and pop() operations take O(1) time in the worst case. So, time complexity = O(n).

In the worst-case, the stack can take up to n elements. Space complexity = O(n)

Note: If(height[i] > height[S.top()]), then the tower at the top of the stack is smaller than the previous tower in the stack and current tower height[i]. In such a scenario, it would form a colored rectangular region and trapped water is equal to the area of that region.

An efficient solution using two pointers approach

Solution Idea

In the last two approaches, we are using extra spaces to get the solution. Can we solve this problem in a single scan without using extra space? Let's explore!

Based on the formula used in the 2nd approach, the water trapped by any tower depends on the minimum of maximum height of towers on both sides. So instead of maintaining two arrays of size n for storing leftMaxHeight and a rightMaxHeight, can we think of maintaining two variables to store the maximum till a given point? Think!

Suppose we search from both the left and right end by maintaining two pointers left and right separately. If there is a larger tower at the right end, then the water trapped would be dependant on the tower's height in the direction from left to right. Similarly, if the tower at the right end is smaller, then the water trapped would be dependant on the tower's height in the direction from right to left. Think!

We first calculate the water trapped on smaller elements out of height[left] and height[right], then move the pointer associated with the smaller element. We move the pointers till the left doesn't cross right. In terms of an analogy, we can think of height[left] and height[right] as a wall of a partial container where we fix the higher one and flow water from the lower part. Think!

Solution Steps

• We declare and Initialise left and right pointers.

• We also Initialise variables trappedWater, leftMaxHeight, and rightMaxHeight.

  int trappedWater = 0
  int leftMaxHeight = 0, rightMaxHeight = 0
  int left = 0, right = n - 1
  

• Now we run a loop to scan the array i.e. while (left <= right)

  1. If (height[left] < height[right]) and (height[left] < leftMaxHeight), then we calculate the trapped water stored by the both towers and increase the left pointer. But if (height[left] > leftMaxHeight), then we update value of leftMaxHeight and increase the left pointer.

  if (height[left] < height[right])
  {
      if (height[left] > leftMaxHeight)
          leftMaxHeight = height[left]
      else
          trappedWater = trappedWater + leftMaxHeight - height[left]
      left = left + 1
  }
  

  2. If (height[left] > height[right]) and height[right] < rightMaxHeight), then we calculate the trapped water stored by the both towers and decrease the right pointer. But if (height[right] > rightMaxHeight), then we update value of rightMaxHeight and decrease the right pointer.

  if (height[left] > height[right])
  {
      if (height[right] > rightMaxHeight)
          rightMaxHeight = height[right]
      else
          trappedWater = trappedWater + rightMaxHeight - height[right]
      right = right - 1
  }
  

• When left > right, then we exit the loop and return the value stored in the trappedWater.

Solution Pseudocode

int rain_water_trapping(int height[], int n)
{
    int trappedWater = 0
    int leftMaxHeight = 0, rightMaxHeight = 0
    int left = 0, right = n - 1
    while (left <= right)
    {
        if (height[left] < height[right])
        {
            if (height[left] > leftMaxHeight)
                leftMaxHeight = height[left]
            else
                trappedWater = trappedWater + leftMaxHeight - height[left]
            left = left + 1
        }
        else
        {
            if (height[right] > rightMaxHeight)
                rightMaxHeight = height[right]
            else
                trappedWater = trappedWater + rightMaxHeight - height[right]                                                            
            right = right - 1
        }
    }
    return trappedWater
}

Solution Analysis

• We are doing a single scan to traverse the array from both ends. After each comparison, we are moving either the left pointer or the right pointer. So in the worst case, we need to do O(n) operations. So, Time complexity = O(n),
• Space complexity = O(1), only constant space is required for variables and pointers.

Critical ideas to think!

• Can we find some other approach to solve this problem in O(n) time and O(1) space? Here is a hint: we first search the maximal tower in height [] and split the array into two halves around it. Now we do two traversals: one from the leftmost tower to the highest tower and another one from the rightmost to the highest tower.
• In the dynamic programming approach, can we save one pass? Here is a hint: Use one array to keep track of maximum height on one side, i.e., left or right. On the other side, we can use a variable to keep track of maximum height so far and process it on the fly during the process when we calculate the volume of water in each tower.
• In the stack-based approach, what would be the best and worst-case scenario?
• In the 4th approach, can we compare leftMaxHeight and rightMaxHeight to decide which pointer to move?
• Let's try a different version of the problem: given an m x n integer matrix height[][] representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.

Comparisons of time and space complexities

• Brute force approach: Time = O(n²), Space = O(1)
• Using Dynamic Programming: Time = O(n), Space = O(n)
• Using Stack: Time = O(n), Space = O(n)
• Using two pointers: Time = O(n), Space = O(1)

Similar coding questions to practice

• Container with most water
• Check for pair in an array with a given sum
• Check whether an array is a subset of another array
• Sort an array of 0s, 1s, and 2s
• Remove duplicates from sorted array
• Equilibrium index of an array
• Find max and min in an array
• Move zeroes to the end of an array
• Valid mountain array
• Roman to Integer
• n Repeated element in 2n size array

Thanks to Navtosh Kumar for his contribution in creating the first version of the content. Please write comments if you find an error or you want to share more insights about the topic. Enjoy learning, Enjoy coding, Enjoy algorithms!