42. Trapping Rain Water

Description:

https://leetcode.com/problems/trapping-rain-water/#/description

Algorithm:

Initially I thought about scan from left to right. and find the containers one by one. However, this doesn’t succeed because It may be trapped in local maximization rather than global maximization.

The correct way is to;

1. scan from left to right and find the left highest for each bar;
2. scan from right to left and find the right highest for each bar;
3. get the water area and add up.

Code:

class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
if (n < 2) return 0;
vector<int> left = vector<int>(n, -1);
vector<int> right = vector<int>(n, -1);
vector<int> thisHeight = vector<int>(n, -1);
left[0] = 0;
right[n – 1] = 0;

int left_rec = 0;
int right_rec = 0;
int total = 0;

for (int i = 1; i < n;i++)
{
if (height[i – 1] >= left_rec)
left_rec = height[i – 1];
left[i] = left_rec;
}
for (int i = n – 2; i >= 0;i–)
{
if (height[i + 1] >= right_rec)
right_rec = height[i + 1];
right[i] = right_rec;
}
for (int i = 0; i < n; i++)
{
int tmp = min(left[i], right[i]) – height[i];
thisHeight[i] = tmp > 0 ? tmp : 0;
total += thisHeight[i];
}
return total;
}
};

Timing:

Scan from left to right: O(n)

Scan from right to left: O(n)

add up: O(n)

Total: 3 * O(n) = O(n)