Leetcode and Lintcode

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;
    }
}