Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) 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.
Example 2:
Input: height = [4,2,0,3,2,5] Output: 9
Constraints:
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
Approach 01:
-
C++
-
Python
#include <bits/stdc++.h>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> getLeftSideArray(vector<int>& height, int n) {
vector<int> leftMax(n);
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
leftMax[i] = max(leftMax[i-1], height[i]);
}
return leftMax;
}
vector<int> getRightSideArray(vector<int>& height, int n) {
vector<int> rightMax(n);
rightMax[n-1] = height[n-1];
for (int i = n-2; i >= 0; i--) {
rightMax[i] = max(rightMax[i+1], height[i]);
}
return rightMax;
}
int trap(vector<int>& height) {
int n = height.size();
vector<int> leftMax = getLeftSideArray(height, n);
vector<int> rightMax = getRightSideArray(height, n);
int sum = 0;
for (int i = 0; i < n; i++) {
int h = min(leftMax[i], rightMax[i]) - height[i];
sum += max(h, 0);
}
return sum;
}
};
from typing import List
class Solution:
def get_left_side_array(self, height: List[int], n: int) -> List[int]:
left_max = [0] * n
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i - 1], height[i])
return left_max
def get_right_side_array(self, height: List[int], n: int) -> List[int]:
right_max = [0] * n
right_max[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
right_max[i] = max(right_max[i + 1], height[i])
return right_max
def trap(self, height: List[int]) -> int:
n = len(height)
left_max = self.get_left_side_array(height, n)
right_max = self.get_right_side_array(height, n)
total_water = 0
for i in range(n):
h = min(left_max[i], right_max[i]) - height[i]
total_water += max(h, 0)
return total_water
Time Complexity:
- get_left_side_array Method: O(n)
- The method iterates through the ‘height’ list once, resulting in a linear time complexity.
- get_right_side_array Method: O(n)
- Similar to ‘get_left_side_array’, this method also iterates through the ‘height’ list once.
- trap Method: O(n)
- This method iterates through the ‘height’ list once, while calling the helper methods ‘get_left_side_array’ and ‘get_right_side_array’, which are both O(n).
Space Complexity:
- get_left_side_array Method: O(n)
- It creates a new list ‘left_max’ of size ‘n’, where ‘n’ is the length of the ‘height’ list.
- get_right_side_array Method: O(n)
- It creates a new list ‘right_max’ of size ‘n’, similar to ‘get_left_side_array’.
- trap Method: O(n)
- This method stores the ‘left_max’ and ‘right_max’ lists, each of size ‘n’, resulting in O(n) space complexity.
Approach 02:
-
C++
-
Python
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
vector<int> left_max(n, -1);
vector<int> right_max(n, -1);
left_max[0] = height[0];
right_max[n-1] = height[n-1];
for (int i = 1; i < n; i++) {
left_max[i] = max(left_max[i-1], height[i]);
}
for (int i = n-2; i >= 0; i--) {
right_max[i] = max(right_max[i+1], height[i]);
}
int total = 0;
for (int i = 0; i < n; i++) {
int h = min(left_max[i], right_max[i]) - height[i];
total += max(h, 0);
}
return total;
}
};
from typing import *
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
left_max = [-1]*n
right_max = [-1]*n
left_max[0] = height[0]
right_max[n-1] = height[n-1]
for i in range(n):
left_max[i] = max(left_max[i-1],height[i])
for i in range(n-2, -1, -1):
right_max[i] = max(right_max[i+1],height[i])
total = 0
for i in range(n):
h = min(left_max[i], right_max[i]) - height[i]
total += max(h,0)
return total
Explanation of the Algorithm
The algorithm aims to calculate the amount of water that can be trapped between the bars represented by the height list.
- Initialization: Two arrays, left_max and right_max, are created to store the maximum height to the left and right of each position.
- Filling left_max array: Iterate through the height list from left to right, and at each position, store the maximum height encountered so far.
- Filling right_max array: Iterate through the height list from right to left, and at each position, store the maximum height encountered so far.
- Calculating trapped water: For each position in the height list, the amount of water trapped is determined by the minimum of the maximum heights to the left and right, minus the height at the current position. The result is summed to get the total trapped water.
This approach ensures that we only pass through the height list a few times, resulting in efficient computation with linear time complexity.
Time Complexity
- Constructing the left_max array:
This involves iterating through the height list once to determine the maximum height to the left of each position. Therefore, it takes O(n) time.
- Constructing the right_max array:
This involves iterating through the height list once in reverse to determine the maximum height to the right of each position. Therefore, it also takes O(n) time.
- Calculating the trapped water:
After constructing the two arrays, the algorithm iterates through the height list once more to calculate the amount of water trapped at each position. This also takes O(n) time.
Total Time Complexity: O(n) since each of the above steps involves a single pass through the height list.
Space Complexity
- left_max array:
An array of the same size as the height list is created to store the maximum height to the left of each position. This requires O(n) space.
- right_max array:
An array of the same size as the height list is created to store the maximum height to the right of each position. This requires O(n) space.
Total Space Complexity: O(n) since we are using two additional arrays of the same size as the input list.