Trapping Rain Water Editorial

Practice Problem Link: Trapping Rain Water

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array A where each element denotes the height of blocks, calculate the total volume of water that can be trapped when it rains. 

Note: one cubic block has a volume of 1 unit.

Naive Approach

The simple solution is to traverse the array and for each array element find the maximum height on the left and right side of the element in the array. Take the difference of the current element from the minimum of those two heights and add it to the answer.

Analysis

• Time Complexity: O(n2)
• Auxiliary Space Complexity: O(1)

Implementation

C++

int volumeOfTrappedRainWater(vector<int> &heights) {
    int n = heights.size();
	int totalRainWater = 0;
	for (int i = 0; i < n; i++){
		int maxLeft = 0, maxRight = 0;
		for (int j = 0; j <= i; j++){
			maxLeft = max (maxLeft, heights[j]);
		}
		for (int j = i; j < n; j++) {
			maxRight = max (maxRight, heights[j]);
		}
		totalRainWater += min (maxRight, maxLeft) - heights[i];
	}
	return totalRainWater;
}

Java

class Solution {
	int volumeOfTrappedRainWater(int[] heights) {
	    int n = heights.length;
		int totalRainWater = 0;
		for (int i = 0; i < n; i++){
			int maxLeft = 0, maxRight = 0;
			for (int j = 0; j <= i; j++){
				maxLeft = Math.max (maxLeft, heights[j]);
			}
			for (int j = i; j < n; j++) {
				maxRight = Math.max (maxRight, heights[j]);
			}
			totalRainWater += Math.min (maxRight, maxLeft) - heights[i];
		}
		return totalRainWater;
	}
}

Optimal Approach

The problem can be solved efficiently with the help of a stack.

• Create an empty stack say index to store the indices.
• Traverse the array and for each index i, while the stack is non-empty and heights[i] is greater than the current top value in the stack. Remove that value from the stack and store it in prevIndx.
• If the stack is not empty, calculate the height as min(heights[i], heights[index.top()]) - heights[prevIndx].
• Calculate the distance between the current array index and the current top index of the stack, multiply it with the height and add it to the answer.
• Push the current array index in the stack.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

int volumeOfTrappedRainWater(vector<int> &heights) {
    int n = heights.size();
	int totalRainWater = 0;
	stack<int> index;
	for (int i = 0; i < n; i++){
		while (!index.empty() && heights[index.top()] < heights[i]){
			int prevIndx = index.top();
			index.pop();
			if (!index.empty()) {
				int height = min (heights[i], heights[index.top()]) - heights[prevIndx];
				totalRainWater += height * (i - 1 - index.top());
			}
		}
		index.push(i);
	}
	return totalRainWater;
}

Java

class Solution {
	int volumeOfTrappedRainWater(int[] heights) {
	    int n = heights.length;
		int totalRainWater = 0;
		Stack<Integer> index = new Stack<> ();
		for (int i = 0; i < n; i++){
			while (!index.isEmpty() && heights[index.peek()] < heights[i]){
				int prevIndx = index.peek();
				index.pop();
				if (!index.isEmpty()) {
					int height = Math.min (heights[i], heights[index.peek()]) - heights[prevIndx];
					totalRainWater += height * (i - 1 - index.peek());
				}
			}
			index.push(i);
		}
		return totalRainWater;
	}
}

Another Approach

This problem can be solved using constant space with the help of two pointers approach.

• Take two pointers say left and right, pointing to the start and end of the given array and do the following while left is less than or equal to right.
• If the array value at the left index is less than or equal to the array value at the right index then add the effective volume trapped at the left index and increment the left index. 
• Otherwise, add the effective volume at the right index and decrement the right index. 
• Also, keep updating the maximum height on the left and right sides to compute the effective volume at each index.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

int volumeOfTrappedRainWater(vector<int> &heights) {
    int left = 0; 
	int right = heights.size() - 1;
	int volume = 0;
	int maxLeft = 0, maxRight = 0;
	while (left <= right) {
		if (heights[left] <= heights[right]) {
			if (heights[left] >= maxLeft) {
				maxLeft = heights[left];
			} else {
				volume += maxLeft - heights[left];
			}
			left++;
		} else {
			if (heights[right] >= maxRight) {
				maxRight = heights[right];
			} else {
				volume += maxRight - heights[right];
			}
			right--;
		}
	}
	return volume;
}

Java

class Solution {
	int volumeOfTrappedRainWater(int[] heights) {
		int left = 0; 
		int right = heights.length - 1;
		int volume = 0;
		int maxLeft = 0, maxRight = 0;
		while (left <= right) {
			if (heights[left] <= heights[right]) {
				if (heights[left] >= maxLeft) {
					maxLeft = heights[left];
				} else {
					volume += maxLeft - heights[left];
				}
				left++;
			} else {
				if (heights[right] >= maxRight) {
					maxRight = heights[right];
				} else {
					volume += maxRight - heights[right];
				}
				right--;
			}
		}
		return volume;
	}
}