Trapping Rain Water Problem
Application of Concept of Lower Envelope of Line Segments

Feedback:
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
https://thealgorists.com/Feedback.

Blogging: If you want to see your publication on
"The Algorists" Blog, send your technical articles to
admin@thealgorists.com .
 Success Story: If https://www.thealgorists.com/Algo has helped you in any way, we would love to hear about it here https://www.thealgorists.com/YourStory .
What is Lower Envelope ?
Given a set of N unsorted, unordered line segments, the lower envelope of these line segments will be the collection of the lowest points (i.e, points with lowest ycoordinates) in the plane.We can easily compute Lower Envelope using Sweep Line Algorithm.
We will discuss a problem below where we will be using Lower Envelope concept to solve the problem.
Problem Statement:
Given n nonnegative integers representing an elevation map where the width of each bar is 1 unit, compute how much water it is able to trap after raining.Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6
If you think through the problem for some time, you would soon be able to figure that
for each bar, to determine how much water will be accumulated on the bar we would need to know two things:
 What is the height of the highest bar on its left (including the current bar) ? Let's call it leftMax.
 What is the height of the highest bar on its right (including the current bar) ? Let's call it rightMax.
Let's suppose f(i) gives the value of the minimum of the two heights of the highest bar on the left and right of the ith bar, say bars[i], then
f(i) = min(max(bars[0...i]), max(bars[i...n  1)) = min(leftMax, rightMax)
It is important to observe that, if the height of the current bar is more that the minimum of the two heights of the left and right highest bars, then no water would be accumulated on that bar.
Below is a simple implementation which takes O(n) time and O(n) space, where n = total number of bars.
Since we need to calculate accumulated water on each bar, O(n) time is the best we can do. If you think more on how to optimize the solution for this problem, you would see that the optimization of the solution for this problem boils down to how efficiently we can compute the minimum of the heights of the left and right highest bar. While discussing the optimization we will see that, this optimization would primarily involve space optimization.
Let's look at the simple solution below which we will go on optimizing.
class Solution {
// non optimized lower envelope based algorithm
// time complexity: O(n)
// space complexity: O(n) > can be further optimized
public int trapRainWater(int[] height) {
if (height == null  height.length == 0) {
return 0;
}
int len = height.length;
int[] leftMaxes = new int[len];
int[] rightMaxes = new int[len];
leftMaxes[0] = height[0];
rightMaxes[len  1] = height[len  1];
for (int i = 1; i < len; i++) {
leftMaxes[i] = Math.max(leftMaxes[i  1], height[i]); // leftMax including the value
// of the current element i.e, [0, i], not [0, n  1]
}
for (int i = len  2; i >= 0; i) {
rightMaxes[i] = Math.max(rightMaxes[i + 1], height[i]); // rightMax including the value
// of the current element, i.e, [i, n  1], not [i+1, n  1]
}
int sum = 0;
for (int i = 0; i < len; i++) {
int lowerEnvelopeAtCurrentLocation = Math.min(leftMaxes[i], rightMaxes[i]);
sum += lowerEnvelopeAtCurrentLocation  height[i];
}
return sum;
}
}
So, from the above discussion we have seen that the hurdle to solve the problem is to find the right maximum and left maximum. We have already seen the function f(i) = min(max(bars[0...i]), max(bars[i...n  1)).
Let's see how the leftMax and rightMax would look like for bar[i], for i = 0 to (n  1).
leftMax[0] = input[0]
rightMax[n  1] = input[n  1]
rightMax[n  1] = input[n  1]
input[] = [0,1,0,2,1,0,1,3,2,1,2,1]
leftMax = [0,1,1,1,2,2,2,3,3,3,3,3]
rightMax= [3,3,3,3,3,3,3,3,2,2,2,1]
leftMax curve would look like:
4  _________________ 3  ___________/ 2  __________/ 1 __/________________________________________ 0 1 2 3 4 5 6 7 8 9 10 11
rightMax curve would look like:
4 _________________________ 3  \________________ 2  \_ 1 ____________________________________________ 0 1 2 3 4 5 6 7 8 9 10 11
If we plot both leftMax and rightMax in the same graph we get below curve for leftMax would look like:
leftMax and rightMax combined curve: 4 ____________________________________________ 3  ___________/ \____________ 2  ___________/ \_ 1 _/__________________________________________ 0 1 2 3 4 5 6 7 8 9 10 11
What are important here to notice here are:
 leftMax is nondecreasing, from index 0 to n1. It either remains constant or increases in value.
 rightMax is nonincreasing, from index 0 to n1. It either remains constant or decreases in value.
minOfLeftMaxRightMax[] = [0,1,1,1,2,2,2,3,2,2,2,1]
Graph for the Lower Envelope would look like:
min of leftMax and rightMax: 4  ___ 3  ___________/ \____________ 2  ___________/ \_ 1 _/__________________________________________ 0 1 2 3 4 5 6 7 8 9 10 11If you have already noticed, The above curve is the LOWER ENVELOPE of leftMax and RightMax combined curve. We get this curve by taking the minimum of the leftMax curve and rightMax curve for all index i.
This problem is all about finding the LOWER ENVELOPE of leftMax curve and rightMax curve for all index i = 0 to n1.
If we want to optimize the previous solution, we should think about how to avoid computing leftMax and rightMax for all index i = 0 to n1, because computing them separately takes O(n) space, which we are trying to optimize. To achieve this, let's reanalyze the characteristics of the different curves we plotted above.
From above plotted curves, our observations are:
 We have two MONOTONIC curve: leftMax and rightMax.
 leftMax curve is monotonically nondecreasing from left to right (i.e, from index 0 to n1).
 rightMax curve is monotonically nonincreasing from left to right (i.e, from index 0 to n1). Or, we can say, rightMax is nondecreasing from right to left from index n1 to 0.
input[] = [0,1,1,1,2,2,2,3,2,1,2,1]
We will have two pointers i and j and iterate over input array. Below is how we can create the lower envelope for all the indices 0 to n1:

i = 0
j = 11
input[i] = 0
input[j] = 1
leftMax is 0 at index = i = 0.
leftMax is monotonically nondecreasing from left to right on index (0 to n1). Which means, leftMax will either stay at 0 or will go up for higher index. So at index = j = 11 leftMax will be at least 0.
rightMax at index = j = 11 is 1. rightMax is nondecreasing from right to left (from index = n1 to 0). This means, rightMax at index = i = 0 is at least 1.
So, minOfLeftMaxRightMax[0] = min(leftMax, rightMax) = min(0, at least 1) = 0
But, we cannot say the same thing about minOfLeftMaxRightMax[11]. At index = j = 11, we have rightMax = 1. We do not know what the true leftMax for index 11 will be as of now. All we can say we leftMax will be at least 0.
If leftMax[11] turns out to be > 1 then minOfLeftMaxRightMax[11] = leftMax[11], but if leftMax stays at 0 or grows higher only to 1, then minOfLeftMaxRightMax[11] = leftMax.

Since we got the true minOfLeftMaxRightMax value for minOfLeftMaxRightMax[0] we increment i by 1
to make i = 1.
j stays at index 11.  Repeat above step till we have LOWER ENVELOPE for all indices.
The below code will make the whole algorithm very clear.
class Solution {
// optimized lower envelope based solution
// O(1) space > optimized
// O(n) time
public int trapRainWater(int[] height) {
if (height == null  height.length == 0) {
return 0;
}
int len = height.length;
int beg = 0;
int end = len  1;
int sum = 0;
int leftMax = height[0];
int rightMax = height[len  1];
while (beg <= end) {
if (leftMax < rightMax) {
/* leftMax is the true value of the lower envelope at this index because
1. current leftMax is the true leftMax for this index (max(height[0...beg]))
2. true rightMax for the current index will be >= current value of rightMax, since rightMax is nonincreasing
from 0 to n  1, i.e, nondecreasing from n  1 to 0
3. leftMax < current value of rightMax
4. rightMax has been calculated from n  1 till current end index.
leftMax has been calculated from 0 to all the way till index beg
True lower envelop value at this location/index = Min(leftMax, >= current value of rightMax) where leftMax <= rightMax
*/
sum += Math.max(leftMax  height[beg], 0);
leftMax = Math.max(leftMax, height[beg]);
beg++;
} else { // leftMax >= rightMax
/* rightMax is the true value of the lower envelope at this index because
1. current rightMax is the true rightMax for this index (max(height[end...n  1]))
2. true leftMax at index end will be >= current value of leftMax, since leftMax is nondecreasing from index 0 to n  1
3. rightMax <= leftMax
4. rightMax has been calculated from n  1 all the way till current end index.
leftMax has been calculated from 0 to till current beg index. So leftMax may not be the
true leftMax for this current index.
True lower envelop value at this location/index = Min(leftMax, >= current value of rightMax) where leftMax <= rightMax
*/
sum += Math.max(rightMax  height[end], 0);
rightMax = Math.max(rightMax, height[end]);
end;
}
}
return sum;
}
}
Another similar implementation :
class Solution {
// optimized lower envelope
// O(1) space > optimized
// O(n) > time
public int trapRainWater(int[] height) {
if (height == null  height.length == 0) {
return 0;
}
int len = height.length;
int beg = 0;
int end = len  1;
int sum = 0;
int leftMax = Integer.MIN_VALUE;
int rightMax = Integer.MIN_VALUE;
while (beg < end) {
if (height[beg] < height[end]) {
leftMax = Math.max(leftMax, height[beg]);
sum += leftMax  height[beg];
beg++;
} else {
rightMax = Math.max(rightMax, height[end]);
sum += rightMax  height[end];
end;
}
}
return sum;
}
}
Yet Another Approach:
Another O(n) time and O(1) space solution would be to find the index of the highest bar (say, H_{max}) and then processing the bars on the left and right of it. For computing for the bars on left of the highest bar H_{max}, we would need to compute only the height of the highest bar on the left of the current bar.
 For computing for the bars on right of the highest bar H_{max}, we would need to compute only the height of the highest bar on the right of the current bar.
This approach does not use Lower Envelope concept.
The code for this approach is given below:
class Solution {
public int trapRainWater(int[] height) {
if (height == null  height.length == 0) {
return 0;
}
int indexOfMaxHeight = 0;
for (int i = 1; i < height.length; i++) {
if (height[i] > height[indexOfMaxHeight]) {
indexOfMaxHeight = i;
}
}
int secondMax = Integer.MIN_VALUE;
int res = 0;
for (int i = 0; i < indexOfMaxHeight; i++) {
secondMax = Math.max(height[i], secondMax);
res += secondMax  height[i];
}
secondMax = height[height.length  1];
for (int i = height.length  1; i > indexOfMaxHeight; i) {
secondMax = Math.max(secondMax, height[i]);
res += secondMax  height[i];
}
return res;
}
}