Trapping Rain Water [Good Problem]

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

Solution:

class Solution {
public:
    int trap(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function

        int sum = 0;
        int firstWalk[n];
        int secondWalk[n];

        // Store the max from front.
        currMax = A[0];
        firstWalk[0] = A[0];
        for (int i = 1; i < n; i++) {
            if (A[i] >= currMax) {
                currMax = A[i];
            }
            firstWalk[i] = currMax;
        }

        // Do it in opposite way. (Store the max from back)
        currMax = A[n-1];
        secondWalk[n-1] = currMax;  
        for (int i = n - 1; i >=0; i--) {
            if (A[i] > currMax) {
                currMax = A[i];
            }
            secondWalk[i] = currMax;
        }
     
        for (int i = 0; i < n; i++ ) {
            // Now firstWalk is having minimum values.
            if (firstWalk[i] < secondWalk[i]) {
                firstWalk[i] = firstWalk[i];
            } else {
                firstWalk[i] = secondWalk[i];
            }
            // Now secondWalk is having accumulated water corresponding to each index.
            secondWalk[i] = firstWalk[i] - A[i];
        }
     
        for (int i = 0; i < n ; i++)
            sum += secondWalk[i];
     
        return sum;
    }
};

==========

Approach 1: Brute force

Intuition

Do as directed in question. For each element in the array, we find the maximum level of water it can trap after the rain, which is equal to the minimum of maximum height of bars on both the sides minus its own height.

Algorithm

• Initialize $ans=0$
• Iterate the array from left to right:
  • Initialize $\text{max\_left}=0$ and $\text{max\_right}=0$
  • Iterate from the current element to the beginning of array updating:
    • $\text{max\_left}=\max(\text{max\_left},\text{height}[j])$
  • Iterate from the current element to the end of array updating:
    • $\text{max\_right}=\max(\text{max\_right},\text{height}[j])$
  • Add $\min(\text{max\_left},\text{max\_right}) - \text{height}[i]$ to $\text{ans}$

Complexity Analysis

• Time complexity: $O(n^2)$. For each element of array, we iterate the left and right parts.
• Space complexity: $O(1)$ extra space. 
  

---

Approach 2: Dynamic Programming

Intuition

In brute force, we iterate over the left and right parts again and again just to find the highest bar size upto that index. But, this could be stored. Voila, dynamic programming.

The concept is illustrated as shown:

Algorithm

• Find maximum height of bar from the left end upto an index i in the array $\text{left\_max}$.
• Find maximum height of bar from the right end upto an index i in the array $\text{right\_max}$.
• Iterate over the $\text{height}$ array and update ans:
  • Add $\min(\text{max\_left}[i],\text{max\_right}[i]) - \text{height}[i]$ to $ans$

Complexity analysis

• Time complexity: $O(n)$.
  • We store the maximum heights upto a point using 2 iterations of $O(n)$ each.
  • We finally update $\text{ans}$ using the stored values in $O(n)$.
• Space complexity: $O(n)$ extra space.
  • Additional $O(n)$ space for $\text{left\_max}$ and $\text{right\_max}$ arrays than in Approach 1. 
    

---

Approach 3: Using stacks

Intuition

Instead of storing the largest bar upto an index as in Approach 2, we can use stack to keep track of the bars that are bounded by longer bars and hence, may store water. Using the stack, we can do the calculations in only one iteration.

We keep a stack and iterate over the array. We add the index of the bar to the stack if bar is smaller than or equal to the bar at top of stack, which means that the current bar is bounded by the previous bar in the stack. If we found a bar longer than that at the top, we are sure that the bar at the top of the stack is bounded by the current bar and a previous bar in the stack, hence, we can pop it and add resulting trapped water to $\text{ans}$.

Algorithm

• Use stack to store the indices of the bars.
• Iterate the array:
  • While stack is not empty and $\text{height}[current]>\text{height}[st.top()]$
    • It means that the stack element can be popped. Pop the top element as $\text{top}$.
    • Find the distance between the current element and the element at top of stack, which is to be filled. $\text{distance} = \text{current} - \text{st.top}() - 1$
    • Find the bounded height $\text{bounded\_height} = \min(\text{height[current]}, \text{height[st.top()]}) - \text{height[top]}$
    • Add resulting trapped water to answer $\text{ans} \mathrel{+}= \text{distance} \times \text{bounded\_height}$
  • Push current index to top of the stack
  • Move $\text{current}$ to the next position

Complexity analysis

• Time complexity: $O(n)$.
  • Single iteration of $O(n)$ in which each bar can be touched at most twice(due to insertion and deletion from stack) and insertion and deletion from stack takes $O(1)$ time.
• Space complexity: $O(n)$. Stack can take upto $O(n)$ space in case of stairs-like or flat structure. 
  

---

Approach 4: Using 2 pointers

Intuition

As in Approach 2, instead of computing the left and right parts seperately, we may think of some way to do it in one iteration. From the figure in dynamic programming approach, notice that as long as $\text{right\_max}[i]>\text{left\_max}[i]$ (from element 0 to 6), the water trapped depends upon the left_max, and similar is the case when $\text{left\_max}[i]>\text{right\_max}[i]$ (from element 8 to 11). So, we can say that if there is a larger bar at one end (say right), we are assured that the water trapped would be dependant on height of bar in current direction (from left to right). As soon as we find the bar at other end (right) is smaller, we start iterating in opposite direction (from right to left). We must maintain $\text{left\_max}$ and $\text{right\_max}$ during the iteration, but now we can do it in one iteration using 2 pointers, switching between the two.

Algorithm

• Initialize $\text{left}$ pointer to 0 and $\text{right}$ pointer to size-1
• While $\text{left}< \text{right}$, do:
  • If $\text{height[left]}$ is smaller than $\text{height[right]}$
    • If $\text{height[left]} \geq \text{left\_max}$, update $\text{left\_max}$
    • Else add $\text{left\_max}-\text{height[left]}$ to $\text{ans}$
    • Add 1 to $\text{left}$.
  • Else
    • If $\text{height[right]} \geq \text{right\_max}$, update $\text{right\_max}$
    • Else add $\text{right\_max}-\text{height[right]}$ to $\text{ans}$
    • Subtract 1 from $\text{right}$.

1 / 11

Complexity analysis

• Time complexity: $O(n)$. Single iteration of $O(n)$.
• Space complexity: $O(1)$ extra space. Only constant space required for $\text{left}$, $\text{right}$, $\text{left\_max}$ and $\text{right\_max}$.

Approach 1: Brute force

Intuition

Do as directed in question. For each element in the array, we find the maximum level of water it can trap after the rain, which is equal to the minimum of maximum height of bars on both the sides minus its own height.

Algorithm

• Initialize $ans=0$
• Iterate the array from left to right:
  • Initialize $\text{max\_left}=0$ and $\text{max\_right}=0$
  • Iterate from the current element to the beginning of array updating:
    • $\text{max\_left}=\max(\text{max\_left},\text{height}[j])$
  • Iterate from the current element to the end of array updating:
    • $\text{max\_right}=\max(\text{max\_right},\text{height}[j])$
  • Add $\min(\text{max\_left},\text{max\_right}) - \text{height}[i]$ to $\text{ans}$

Complexity Analysis

• Time complexity: $O(n^2)$. For each element of array, we iterate the left and right parts.
• Space complexity: $O(1)$ extra space. 
  

---

Approach 2: Dynamic Programming

Intuition

In brute force, we iterate over the left and right parts again and again just to find the highest bar size upto that index. But, this could be stored. Voila, dynamic programming.

The concept is illustrated as shown:

Algorithm

• Find maximum height of bar from the left end upto an index i in the array $\text{left\_max}$.
• Find maximum height of bar from the right end upto an index i in the array $\text{right\_max}$.
• Iterate over the $\text{height}$ array and update ans:
  • Add $\min(\text{max\_left}[i],\text{max\_right}[i]) - \text{height}[i]$ to $ans$

Complexity analysis

• Time complexity: $O(n)$.
  • We store the maximum heights upto a point using 2 iterations of $O(n)$ each.
  • We finally update $\text{ans}$ using the stored values in $O(n)$.
• Space complexity: $O(n)$ extra space.
  • Additional $O(n)$ space for $\text{left\_max}$ and $\text{right\_max}$ arrays than in Approach 1. 
    

---

Approach 3: Using stacks

Intuition

Instead of storing the largest bar upto an index as in Approach 2, we can use stack to keep track of the bars that are bounded by longer bars and hence, may store water. Using the stack, we can do the calculations in only one iteration.

We keep a stack and iterate over the array. We add the index of the bar to the stack if bar is smaller than or equal to the bar at top of stack, which means that the current bar is bounded by the previous bar in the stack. If we found a bar longer than that at the top, we are sure that the bar at the top of the stack is bounded by the current bar and a previous bar in the stack, hence, we can pop it and add resulting trapped water to $\text{ans}$.

Algorithm

• Use stack to store the indices of the bars.
• Iterate the array:
  • While stack is not empty and $\text{height}[current]>\text{height}[st.top()]$
    • It means that the stack element can be popped. Pop the top element as $\text{top}$.
    • Find the distance between the current element and the element at top of stack, which is to be filled. $\text{distance} = \text{current} - \text{st.top}() - 1$
    • Find the bounded height $\text{bounded\_height} = \min(\text{height[current]}, \text{height[st.top()]}) - \text{height[top]}$
    • Add resulting trapped water to answer $\text{ans} \mathrel{+}= \text{distance} \times \text{bounded\_height}$
  • Push current index to top of the stack
  • Move $\text{current}$ to the next position

Complexity analysis

• Time complexity: $O(n)$.
  • Single iteration of $O(n)$ in which each bar can be touched at most twice(due to insertion and deletion from stack) and insertion and deletion from stack takes $O(1)$ time.
• Space complexity: $O(n)$. Stack can take upto $O(n)$ space in case of stairs-like or flat structure. 
  

---

Approach 4: Using 2 pointers

Intuition

As in Approach 2, instead of computing the left and right parts seperately, we may think of some way to do it in one iteration. From the figure in dynamic programming approach, notice that as long as $\text{right\_max}[i]>\text{left\_max}[i]$ (from element 0 to 6), the water trapped depends upon the left_max, and similar is the case when $\text{left\_max}[i]>\text{right\_max}[i]$ (from element 8 to 11). So, we can say that if there is a larger bar at one end (say right), we are assured that the water trapped would be dependant on height of bar in current direction (from left to right). As soon as we find the bar at other end (right) is smaller, we start iterating in opposite direction (from right to left). We must maintain $\text{left\_max}$ and $\text{right\_max}$ during the iteration, but now we can do it in one iteration using 2 pointers, switching between the two.

Algorithm

• Initialize $\text{left}$ pointer to 0 and $\text{right}$ pointer to size-1
• While $\text{left}< \text{right}$, do:
  • If $\text{height[left]}$ is smaller than $\text{height[right]}$
    • If $\text{height[left]} \geq \text{left\_max}$, update $\text{left\_max}$
    • Else add $\text{left\_max}-\text{height[left]}$ to $\text{ans}$
    • Add 1 to $\text{left}$.
  • Else
    • If $\text{height[right]} \geq \text{right\_max}$, update $\text{right\_max}$
    • Else add $\text{right\_max}-\text{height[right]}$ to $\text{ans}$
    • Subtract 1 from $\text{right}$.

1 / 11

Complexity analysis

• Time complexity: $O(n)$. Single iteration of $O(n)$.
• Space complexity: $O(1)$ extra space. Only constant space required for $\text{left}$, $\text{right}$, $\text{left\_max}$ and $\text{right\_max}$.