Trapping Rain Water

Problem:

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.


The above elevation map 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. Thanks Marcos for contributing this image!

Leetcode link
Lintcode link

My solution:

For each bar, find the highest bars of the left side and right side respectively.
The trapping water for the bar is min(leftMax,rightmax) - its height.

There are two solutions.

    • Find the highest bar
    • Process the left and right of the highest bar respectively
    • Go through the bars from left to right, calculate the left highest bar for each bar
    • Go through the bars form right to left, calculate the left highest bar for each bar
    • Calculate the min(leftMax,rightmax) - its height for each bar.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/*************************************************************************
> File Name: TrappingWater.java
> Author: Yao Zhang
> Mail: psyyz10@163.com
> Created Time: Fri 13 Nov 10:45:30 2015
************************************************************************/


public class TrappingWater{
// Solution 1
public int trap(int[] height){
int area = 0;
int maxIndex = 0;

// Find the index of the highest bar
for (int i = 0; i < height.length; i ++){
if (height[i] > height[maxIndex])
maxIndex = i;
}

// Process the left side of the highest bar
int leftMax = 0;
for (int i = 0; i < maxIndex; i++){
if (height[i] > leftMax)
leftMax = height[i];
else
area += leftMax - height[i];
}

// Process the rigtht side of the highest bar
int rightMax = 0;
for (int i = height.length - 1; i > maxIndex; i--){
if (height[i] > rightMax)
rightMax = height[i];
else
area += rightMax - height[i];
}

return area;
}

// Solution 2
public int trap2(int[] height){
int area = 0;

if (height.length == 0)
return area;

// find the left highest bar value for each bar
int[] leftMax = new int[height.length];
leftMax[0] = 0;
for (int i = 1; i < height.length; i++){
leftMax[i] = Math.max(height[i-1], leftMax[i-1]) ;
}

// for each bar, calculate the trapping water by
// calculating min(leftMax,rightmax) - height
int max = 0;
for (int i = height.length - 1; i > 0; i--){
int diff = Math.min(max,leftMax[i]) - height[i];
area += diff > 0 ? diff : 0;
max = Math.max(height[i], max);
}

return area;
}
}