Problem Statement
Given an integer array A[] consisting of N non-negative integers representing an elevation map, where the width of each bar is 1. The task is to compute the total volume of water that can be trapped after rain.
Examples :
Input: A[] = { 0,1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 }
Output: 6
Explanation:
The rain water trapped is represented by the blue region.
- Trap 1 unit of water between the first and third block
- Trap 4 units of water between the second and third blocks.
Therefore, the total volume of water is – 1 + 4 + 1 = 6 units.
Algorithm
The key idea to solve this problem is to understand that rainwater can only be trapped if there exists a block of greater height, both on the left and the right side than the current block. Then rainwater can be trapped on top of the block.
So, it can be easily inferred that the amount of water a block can hold is equal to the minimum of the maximum height present on both the left and right half minus the height of the current block.
i.e.
Vol_of_A[i] = min(right_max, left_max) – A[i]
Bruteforce Approach
Since our task is to find the maximum height on the left and right for each element of the array, simply traverse each element of the array A[]. For each element, find the maximum height on the left and the maximum height on the right. At last, add min(right_max, left_max) – A[i] to answer.
Algorithm
- Initialise a variable res to 0, to store the final answer.
- Traverse the array A[] from 1 to N and for each element:
- Initialise left_max = 0 and right_max = 0
- Traverse from A[i] till the beginning and update:
- left_max = max(left_max, A[i])
- Similarly, traverse from A[i] till the end of the array and update:
- right_max = max(right_max, A[i])
Add min(left_max, right_max) – A[i] to res.
C++ Code Implementation
class Solution {
public:
int trapping_rain_water(vector<int>& A) {
int res = 0;
for (int i = 1; i < A.size() - 1; i++) {
//Find left_max
int left_max = INT_MIN;
for (int j = i - 1; j >= 0; j--) {
left_max = max(left_max, A[j]);
}
//Find right_max
int right_max = INT_MIN;
for (int k = i + 1; k < A.size(); k++) {
right_max = max(right_max, A[k]);
}
//Find volume
int maxW = min (left_max,right_max);
res += maxW - A[i];
}
return res;
}
};
Java Code Implementation
public static int trapping_rain_water(int[] A, int N)
{
int res = 0;
for(int i = 0; i < N ; i++)
{
int left_max= arr[i];
for(int j = i - 1; j >= 0; j--)
{
left_max = Math.max(left_max, A[j]);
}
int right_max = A[i];
for(int j = i + 1; j < n; j++)
{
right_max = Math.max(right_max, A[j]);
}
res += Math.min(left_max, right_max) - A[i];
}
return res;
}
Python Code Implementation
def trapping_rain_water(A, N) :
res = 0;
for i in range(1, N - 1) :
left_max = A[i];
for j in range(i) :
left_max = max(left_max, A[j]);
right_max = A[i];
for j in range(i + 1 , n) :
right_max = max(right_max, A[j]);
res = res + (min(left_max, right_max) - A[i]);
return res;
- Time Complexity: O(N^2). For each element, the left and right half are traversed.
- Space Complexity: O(1)
Dynamic Programming Approach
Can we improve the efficiency from O(N^2) to O(N)? Remember, in brute force, we are traversing left and right for each element. What if we store this information, then the problem can be solved using a single traversal, essentially reducing the time complexity to O(N).
The idea is to consider two arrays left_max[] and right_max[], where left_max[i] will store the maximum height on the left until index i. Similarly, right_max[i] will store the maximum height on the right until index i.
Algorithm:
- Initialise two arrays left_max[] and right_max[] of size N.
- Consider a variable mx = 0.
- Traverse from left to right and for each index i, update mx = max(mx, A[i[) and assign left_max = mx.
- Similarly, traverse a loop, N to 1 and for each index i, update mx = max(mx, A[i[) and assign right_max = mx.
- Initialise a variable res = 0 and traverse from 0 to N – 1. For each index i, add min(left_max[i], right_max[i]) – A[i] to res.
C++ Code Implementation
class Solution {
public:
int trapping_rain_water(vector<int>& A)
{
int res = 0;
int N = A.size();
int left_max[N], right_max[N];
int mx = INT_MIN;
for (int i = 0; i < N; i++) {
mx = max(mx, A[i]);
left_max[i] = mx;
}
mx = INT_MIN
for (int i = N - 1; i >= 0; i--) {
mx = max(mx, height[i]);
right_max[i] = mx
}
for (int i = 0; i < N ; i++) {
res += min(left_max[i], right_max[i]) - A[i];
}
return res;
}
};
Java Code Implementation
public int trapping_rain_water(int[] A) {
int res = 0;
if (A.length == 0) {
return 0;
}
int[] leftMax = new int[A.length];
int[] rightMax = new int[A.length];
leftMax[0] = A[0];
for (int i = 1; i < leftMax.length; i++) {
leftMax[i] = Math.max(leftMax[i - 1], A[i]);
}
rightMax[A.length - 1] = A[A.length - 1];
for (int j = rightMax.length - 2; j >= 0; j--) {
rightMax[j] = Math.max(rightMax[j + 1], A[j]);
}
for (int x = 0; x < A.length; x++) {
res += Math.min(leftMax[x], rightMax[x]) - A[x];
}
return res;
}
Python Code Implementation
def trapping_rain_water(self, A: List[int]) -> int:
N = len(A)
left_max = N * [0]
right_max = N * [0]
ans = 0
for i in range(N):
if i == 0:
left_max[i] = Z[i]
right_max[N-1-i] = A[n-1-i]
else:
left_max[i] = max(left_max[i-1], A[i])
right_max[n-1-i] = max(right_max[n-i], A[N-1-i])
for i in range(N):
ans += (min(left_max[i], right_max[i]) - A[i])
return ans
- Time Complexity: O(N) + O(N) + O(N) = O(N), since the array is traversed thrice.
- Space Complexity: O(N), since two arrays are needed.
Approach 3: Using stacks
In DP, the arrays were traversed twice. Can we improve the approach to a single scan? The idea is to keep track of the area between the current block A[i] and all the previous blocks with smaller heights in the array. We can simply use a stack to track the index of the previous smaller blocks.
Algorithm:
- Declare a stack S.
- Traverse the array from left to right:
- If the current block A[i] is larger than the top of the stack i.e. S.top(), it can be inferred that the block at the top of the stack is confined between the current block and the previous block in the stack.
- Therefore, perform S.pop() and add the water that can be stored.
- The total volume of water can be calculated as follows:
- Length = Current index i – S.top() – 1
- Width = min(A[i] – A[S.top()] – A[top]
- Add the total volume to res = Length X Width
C++ Code Implementation
class Solution {
public:
int trapping_rain_water(vector<int>& A)
{
//Final answer
int res = 0;
int N = A.size();
//Stack to store indices
stack<int>S;
int i = 0;
//Traverse through each block
while(i < N){
while(!S.empty() and A[i] > A[S.top()]){
//Store the height of the top
int top = A[S.top()];
S.pop();
if(S.empty()){
break;
}
//Find distance between the left and right height
int length = i - S.top() - 1;
//Finding width
int width = min(A[i], A[S.top()]) - A[top];
//Total volume of water added
res += length * width;
}
S.push(i);
i = i + 1;
}
return res;
}
};
Java Code Implementation
public int trapping_rain_water(int[] A) {
int N = A.length;
int res = 0;
Stack<Integer> stack = new Stack<Integer>();
int i = 0;
while(i < N){
while (!stack.isEmpty() && A[i] > A[stack.peek()]) {
int top = A[stack.peek()];
stack.pop();
if(stack.isEmpty()){
break;
}
int length = i - stack.peek() - 1;
int width = Math.min(A[i], A[stack.peek()]) - A[top];
res += length * width;
if (height[leftIndex] <= height[i]) {
stack.pop();
}
}
stack.push(i);
i = i + 1;
}
return res;
}
Python Code Implementation
def trapping_rain_water(A):
stack = []
res = 0
for i in range(len(A)):
while stack and A[i] > A[stack[-1]]:
pop = stack.pop()
if stack:
left = A[stack[-1]]
right = A[i]
res += (min(right, left) - A[pop])*(i-stack[-1]-1)
stack.append(i)
return res
- Time Complexity: O(N), since the array is traversed once.
- Space Complexity: O(N). Stack takes O(N) space.
Two Pointers Approach
In the last approach, though it is solved using a single traversal, it uses an extra space. Can it be improved to O(1) space?
According to Approach 2, the total volume of water trapped is dependent upon the minimum-maximum of height on the left and right half of the current block. Therefore, instead of considering two arrays to store the heights, we can simply use two variables to store the maximum for the given index. But how?
Take two points, once on the left side of the array and another on the right side. If there is a block on the left, then the total water trapped would be dependent on the direction from right to left and vice versa.
Algorithm:
- Initialise two pointers left = 0 and right = N – 1 and res = 0.
- Initialise two variables left_max = 0 and right_max = 0, denoting the maximum height on the left and maximum height on the right.
- Traverse the array, i.e. while(left <= right)
- If A[left] < A[right] and left_max > A[left]
- Then, add left_max – A[left] to res
- Else if left_max < A[left]
- Update left_max to A[left]
- Increment left pointer
- Similarly, if If A[left] > A[right] and right_max > A[right]
- Then, add right_max – A[right] to res
- Else if right_max < A[right]
- Update right_max to A[right]
- Increment right pointer
- If A[left] < A[right] and left_max > A[left]
- Print res
C++ Code Implementation
class Solution {
public:
int trapping_rain_water(vector<int>& A)
{
int res = 0;
int N = A.size();
int left = 0, right = N - 1;
int left_max = 0, right_max = 0;
while(left <= right){
if(A[left] < A[right]){
if(A[left] > left_max){
left_max = A[left];
}
else{
res += left_max - A[left];
}
left = left + 1;
}
else{
if(A[right] > right_max){
right_max = A[right];
}
else{
res += right_max - A[right];
}
right = right + 1;
}
}
return res;
}
};
Java Code Implementation
public int trapping_rain_water(int[] A) {
int res =0;
int left_max = 0;
int right_max = 0;
int i = 0;
int j = A.length -1;
while(i< j){
left_max = Math.max(left_max, A[i]);
right_max = Math.max(right_max, A[j]);
if(left_max < right_max){
res += left_max-A[i];
i++;
}
else{
res += right_max - A[j];
j--;
}
}
return res;
}
Python Code Implementation
def trapping_rain_water(A):
i, j = 0, len(A) - 1
lMax, rMax = A[i], A[j]
res = 0
while i < j:
left_max = max(left_max, A[i])
right_max = max(right_max, A[j])
if left_max < right_max:
res += left_max - A[i]
i += 1
else:
res += right_max - A[j]
j -= 1
return res
- Time Complexity: O(N), since the array is traversed once.
- Space Complexity: O(1).
Practice Problem
Frequently Asked Questions
Q.1: How many methods are there to solve the trapping rainwater problem?
Ans: There are mainly 4 methods to solve the problem, all are mentioned above.
Q.2: Which is the best approach with respect to the time and space complexity?
Ans: The two-pointer approach is the best approach, it has O(N) time complexity and O(1) space complexity.
