Trapping Rain Water: Calculate Trapped Water in an Array

71.6k
0

Given an integer array height, where height[i] represents the height of a bar, find how much rain water can be trapped between the bars after raining.

Each bar has width 1.

Return the total amount of trapped water.

Example 1

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

Output: 6

Explanation: Water gets trapped between taller bars. The total trapped water is 6 units.

Example 2

Input: height = [4, 2, 0, 3, 2, 5]

Output: 9

Explanation: Water gets trapped at multiple positions between the left and right boundaries.

Brute Force Approach

For water to stay above a bar, it needs boundaries on both sides. The maximum possible water level at index i is therefore decided by the smaller of the tallest bars on its left and right.

So, for every index, find leftMax and rightMax, then calculate the trapped water as min(leftMax, rightMax) - height[i]. This gives the correct answer, but repeatedly scanning both sides for every bar makes the approach inefficient.

Algorithm

  • The size of the array is stored in n. If n is less than 3, 0 is returned because at least three bars are required to trap water between boundaries.

  • A variable totalWater is initialized with 0. This stores the total amount of water trapped across all bars.

  • The array is traversed using index i. Each index is treated as a possible place where water may be stored.

  • For every index i, leftMax is found by scanning all bars from index 0 to i. This gives the tallest boundary available on the left side including the current bar.

  • Similarly, rightMax is found by scanning all bars from index i to n - 1. This gives the tallest boundary available on the right side including the current bar.

  • The water level at index i is calculated as min(leftMax, rightMax), because water can stay only up to the smaller boundary.

  • The water trapped above the current bar is calculated as waterLevel - height[i]. This value is added to totalWater.

  • After all bars are checked, totalWater is returned.

Dry Run

Trapping Rain Water Brute Force Dry Run.png

Trapping Rain Water Brute Force Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Calculates trapped water by
// checking both sides of each bar.
int trap(vector<int>& height) {
int n = height.size();
// At least three bars
// are required to trap water.
if (n < 3) {
return 0;
}
int totalWater = 0;
// Treat each index as a
// possible position for water.
for (int i = 0; i < n; i++) {
int leftMax = 0;
int rightMax = 0;
// Find the tallest boundary
// from the left up to i.
for (int j = 0; j <= i; j++) {
leftMax = max(leftMax, height[j]);
}
// Find the tallest boundary
// from i to the right end.
for (int j = i; j < n; j++) {
rightMax = max(rightMax, height[j]);
}
int waterLevel = min(leftMax, rightMax);
// The space above the bar
// contributes trapped water.
totalWater += waterLevel - height[i];
}
return totalWater;
}
};
int main() {
vector<int> height = {
0, 1, 0, 2, 1, 0,
1, 3, 2, 1, 2, 1
};
Solution solution;
cout << solution.trap(height) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N²), where N is the size of the array. For every index, the left side and right side are scanned again to find leftMax and rightMax.

Space Complexity: O(1), because no extra data structure is used. Only a few variables are maintained.

Better Approach

The brute-force approach repeatedly calculates the tallest bar on the left and right of every index. This repeated work can be removed by precomputing these values.

Store the maximum height up to every index in leftMax and the maximum height from every index to the end in rightMax. Then the trapped water at each position can be calculated directly using min(leftMax[i], rightMax[i]) - height[i], reducing the time to linear at the cost of extra space.

Algorithm

  • The size of the array is stored in n. If n is less than 3, 0 is returned because water cannot be trapped without two boundaries and a middle space.

  • Two arrays, leftMax and rightMax, are created with size n. These arrays store the tallest boundary available from the left and right sides for every index.

  • leftMax[0] is set as height[0]. Then the leftMax array is filled from left to right. For every index i, leftMax[i] stores the maximum value between leftMax[i - 1] and height[i].

  • rightMax[n - 1] is set as height[n - 1]. Then the rightMax array is filled from right to left. For every index i, rightMax[i] stores the maximum value between rightMax[i + 1] and height[i].

  • A variable totalWater is initialized with 0 to store the final amount of trapped water.

  • For every index i, the water level is calculated as min(leftMax[i], rightMax[i]) because the smaller boundary controls the water level.

  • The trapped water at index i is calculated as waterLevel - height[i], and this value is added to totalWater.

  • After all indices are processed, totalWater is returned.

Dry Run

Trapping Rain Water Better Approach Dry Run.png

Trapping Rain Water Better Approach Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Uses prefix and suffix
// maximum boundaries for each bar.
int trap(vector<int>& height) {
int n = height.size();
// At least three bars
// are required to trap water.
if (n < 3) {
return 0;
}
vector<int> leftMax(n);
vector<int> rightMax(n);
leftMax[0] = height[0];
// Build the tallest boundary
// seen from the left side.
for (int i = 1; i < n; i++) {
leftMax[i] = max(
leftMax[i - 1],
height[i]
);
}
rightMax[n - 1] = height[n - 1];
// Build the tallest boundary
// seen from the right side.
for (int i = n - 2; i >= 0; i--) {
rightMax[i] = max(
rightMax[i + 1],
height[i]
);
}
int totalWater = 0;
// Use both boundaries to
// calculate water at each bar.
for (int i = 0; i < n; i++) {
int waterLevel = min(
leftMax[i],
rightMax[i]
);
totalWater +=
waterLevel - height[i];
}
return totalWater;
}
};
int main() {
vector<int> height = {
0, 1, 0, 2, 1, 0,
1, 3, 2, 1, 2, 1
};
Solution solution;
cout << solution.trap(height) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the size of the array. The array is traversed once to build leftMax, once to build rightMax, and once to calculate the trapped water.

Space Complexity: O(N), because two extra arrays, leftMax and rightMax, are used.

Optimal Approach

The prefix and suffix arrays are not necessary if we keep only the maximum boundary seen so far from both sides using leftMax and rightMax.

With two pointers at the ends, process the side having the smaller current height. If height[left] < height[right], a sufficiently high boundary already exists on the right, so the water at left depends only on leftMax. Otherwise, the right side can be decided using rightMax. After processing that position, move the corresponding pointer inward.

This calculates the same water contribution without storing maximum values for every index.

Algorithm

  • The size of the array is stored in n. If n is less than 3, 0 is returned because water cannot be trapped.

  • Two pointers are initialized. left is set to 0, and right is set to n - 1.

  • Two variables, leftMax and rightMax, are initialized with 0. leftMax stores the tallest bar seen so far from the left side, and rightMax stores the tallest bar seen so far from the right side.

  • A variable totalWater is initialized with 0. This stores the total amount of trapped water.

  • While left is less than right, height[left] and height[right] are compared.

  • If height[left] is smaller than height[right], the left side is processed. If height[left] is greater than or equal to leftMax, leftMax is updated because a new left boundary has been found. Otherwise, leftMax - height[left] is added to totalWater because water can be trapped above the current bar. Then left is moved forward.

  • If height[right] is smaller or equal, the right side is processed. If height[right] is greater than or equal to rightMax, rightMax is updated because a new right boundary has been found. Otherwise, rightMax - height[right] is added to totalWater because water can be trapped above the current bar. Then right is moved backward.

  • After the loop ends, totalWater is returned.

Dry Run

Trapping Rain Water Optimal Approach Dry Run.png

Trapping Rain Water Optimal Approach Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Uses two pointers and keeps
// only the required boundaries.
int trap(vector<int>& height) {
int n = height.size();
// At least three bars
// are required to trap water.
if (n < 3) {
return 0;
}
int left = 0;
int right = n - 1;
int leftMax = 0;
int rightMax = 0;
int totalWater = 0;
// Process the side with the
// smaller current boundary.
while (left < right) {
// The left side can be
// decided using leftMax.
if (height[left] < height[right]) {
// Update the left boundary
// when a taller bar appears.
if (height[left] >= leftMax) {
leftMax = height[left];
}
// Otherwise, the gap above
// this bar stores water.
else {
totalWater +=
leftMax - height[left];
}
left++;
}
// The right side can be
// decided using rightMax.
else {
// Update the right boundary
// when a taller bar appears.
if (height[right] >= rightMax) {
rightMax = height[right];
}
// Otherwise, the gap above
// this bar stores water.
else {
totalWater +=
rightMax - height[right];
}
right--;
}
}
return totalWater;
}
};
int main() {
vector<int> height = {
0, 1, 0, 2, 1, 0,
1, 3, 2, 1, 2, 1
};
Solution solution;
cout << solution.trap(height) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the size of the array. Each pointer moves inward at most N times in total.

Space Complexity: O(1), because no extra array is used. Only pointer variables and boundary variables are maintained.

Interview follow-up Questions

Water overflows from the smaller boundary, so the water level cannot go above the smaller of the two boundaries.

Two PointerArrays

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0...

67.1k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.4k
Comments0