Leetcode Problem 32: Trapping Rain Water in go

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.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

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

Solution


Approach 1: Brute force

Intuition

Algorithm

  • Initialize ans=0
  • Iterate the array from left to right:
  • Initialize max_left=0 and max_right=0
  • Iterate from the current element to the beginning of array updating:
    • max_left=max(max_left,height[j])
  • Iterate from the current element to the end of array updating:
    • max_right=max(max_right,height[j])
  • Add min(max_left,max_right)−height[i] to ans

Algorithm

Complexity Analysis

  • Time complexity: O(n^2)O(n2). For each element of array, we iterate the left and right parts.
  • Space complexity: O(1)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 the maximum height of the bar from the left end up to an index i in the array left_max.
  • Find the maximum height of the bar from the right end up to an index i in the array right_max.
  • Iterate over the height array and update ans:
    • Add min(max_left[i],max_right[i])−height[i] to ans
int trap(vector<int>& height)
{
	if(height == null)
		return 0;
    int ans = 0;
    int size = height.size();
    vector<int> left_max(size), right_max(size);
    left_max[0] = height[0];
    for (int i = 1; i < size; i++) {
        left_max[i] = max(height[i], left_max[i - 1]);
    }
    right_max[size - 1] = height[size - 1];
    for (int i = size - 2; i >= 0; i--) {
        right_max[i] = max(height[i], right_max[i + 1]);
    }
    for (int i = 1; i < size - 1; i++) {
        ans += min(left_max[i], right_max[i]) - height[i];
    }
    return ans;
}

Complexity analysis

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

Approach 3: Using stacks

Intuition

Instead of storing the largest bar up to an index as in Approach 2, we can use the 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 the bar is smaller than or equal to the bar at top of the 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}ans.

Algorithm

  • Use stack to store the indices of the bars.
  • Iterate the array:
    • While stack is not empty and height[current]>height[st.top()]
      • It means that the stack element can be popped. Pop the top element as top.
      • Find the distance between the current element and the element at top of stack, which is to be filled. distance=current−st.top()−1
      • Find the bounded_height=min(height[current],height[st.top()])−height[top]
      • Add resulting trapped water to answer ans+=distance×bounded_height
    • Push current index to top of the stack
    • Move current to the next position
int trap(vector<int>& height)
{
    int ans = 0, current = 0;
    stack<int> st;
    while (current < height.size()) {
        while (!st.empty() && height[current] > height[st.top()]) {
            int top = st.top();
            st.pop();
            if (st.empty())
                break;
            int distance = current - st.top() - 1;
            int bounded_height = min(height[current], height[st.top()]) - height[top];
            ans += distance * bounded_height;
        }
        st.push(current++);
    }
    return ans;
}

Complexity analysis

  • Time complexity: O(n).
    • A single iteration of O(n) in which each bar can be touched at most twice(due to insertion and deletion from the stack) and insertion and deletion from stack take O(1) time.
  • Space complexity: O(n). The stack can take up to O(n) space in case of a stairs-like or flat structure.

Approach 4: Using 2 pointers

Intuition

As in Approach 2, instead of computing the left and right parts separately, we may think of some way to do it in one iteration. From the figure in dynamic programming approach, notice that as long as right_max[i]>left_max[i] (from element 0 to 6), the water trapped depends upon the left_max, and similar is the case when left_max[i]>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 the height of the bar in the current direction (from left to right). As soon as we find the bar at another end (right) is smaller, we start iterating in the opposite direction (from right to left). We must maintain left_max and right_max during the iteration, but now we can do it in one iteration using 2 pointers, switching between the two.

Algorithm

  • Initialize left pointer to 0 and right pointer to size-1
  • While left<right, do:
    • If height[left] is smaller than height[right]
      • If height[left]≥left_max, update left_max
      • Else add left_max−height[left] to ans
      • Add 1 to left.
    • Else
      • If height[right]≥right_max, update right_max
      • Else add right_max−height[right] to ans
      • Subtract 1 from right.

C++

int trap(vector<int>& height)
{
    int left = 0, right = height.size() - 1;
    int ans = 0;
    int left_max = 0, right_max = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]);
            ++left;
        }
        else {
            height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]);
            --right;
        }
    }
    return ans;
}

Go

func trap(height []int) int {
    left := 0
    right := len(height) - 1
    ans := 0
    left_max, right_max := 0,0
    
    for left < right {
        if height[left] < height[right] {
            if height[left] >= left_max {
                left_max = height[left]
            } else {
                ans += left_max - height[left]
            }
            
            left++
        } else {
            if height[right] >= right_max {
                right_max = height[right]
            } else {
                ans += right_max - height[right]
            }
            
            right--
        }
    }
    
    return ans
}

If you have any questions, you can comment. I hope, you enjoyed the post. Stay tuned for more interesting posts.

Leave a Reply

Your email address will not be published. Required fields are marked *