42. Trapping Rain Water (Hard)

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

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.

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!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Solutions

class Solution {

    // Sort out all the peaks, then merge the peaks if possible.

    public int trap(int[] height) {
        int ans = 0;

        if (height == null || height.length <= 2) {
            return 0;
        }

        int len = height.length;

        List<Integer> peaks = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            if (i == 0) {
                if (height[0] > height[1]) {
                    peaks.add(0);
                }

                continue;
            }

            if (i == len - 1) {
                if (height[len - 1] > height[len - 2]) {
                    peaks.add(len - 1);
                }

                continue;
            }

            if (height[i] >= height[i - 1] && height[i] >= height[i + 1]) {
                peaks.add(i);
            }
        }

        // the first and last peak should be processed properly. They can merge neighboring
        // peaks if possible rather than merged by others.

        while (peaks.size() > 2) {
            List<Integer> toRemove = new ArrayList<>();

            for (int i = 1; i < peaks.size() - 1; i ++) {

                int left = height[peaks.get(i - 1)];
                int mid = height[peaks.get(i)];
                int right = height[peaks.get(i + 1)];

                // peak[i-1] >= peak[i] <= peak[i+1], then peak[i] is merged
                if (mid <= left && mid <= right) {
                    toRemove.add(peaks.get(i));
                }
            }

            if (toRemove.size() == 0) {
                break;
            }

            peaks.removeAll(toRemove);
        }

        for (int i = 0; i < peaks.size() - 1; i++) {
            int minH = Math.min(height[peaks.get(i)], height[peaks.get(i + 1)]);

            for (int j = peaks.get(i) + 1; j <= peaks.get(i + 1) - 1; j++) {

                // FIXME height[j] may be larger than minnH
                ans += minH <= height[j] ? 0 : minH - height[j];
            }
        }

        return ans;
    }
}

Incorrect Solutions

class Solution {

    // Incorrect Solution
    // Larger container can cover the inner small containers.

    // This problem is relatively easy. The major point is sort all the peak1->valley-peak2 patterns
    // which can hold water and when rain drops. The volume of the water it traps is determined by the
    // relative lower peak.


    public int trap(int[] height) {
        int ans = 0;

        if (height == null || height.length <= 2) {
            return 0;
        }

        int len = height.length;

        int peak1 = -1;
        int peak2 = -1;
        int valley = -1;

        for (int i = 0; i < len; i++) {
            // if it is the first element
            if (i == 0) {
                // set the first peak1
                if (height[0] > height[1]) {
                    peak1 = 0;
                }

                // ignore it if 0 is a valley
            }
            // if the last element
            else if (i == len - 1) {
                // set the last peak2
                if (height[len - 1] > height[len - 2]) {
                    peak2 = len - 1;
                }
                // ignore it if len-1 is a valley
            }
            // lower than both sides
            else if (height[i] < height[i - 1] && height[i] < height[i + 1]) {
                // the left peak must be already determined
                valley = i;
            }
            // higher than both sides
            else if (height[i] > height[i - 1] && height[i] > height[i + 1]) {
                // valley not find yet, set peak1 first
                if (valley < 0) {
                    peak1 = i;
                }
                // valley already set, set it to peak2
                else {
                    peak2 = i;
                }
            }

            // calculate the volume of the container if it is formed.
            if (peak1 >= 0 && peak2 >= 0 && valley >= 0) {
                int minH = Math.min(height[peak1], height[peak2]);
                for (int j = peak1; j <= peak2; j++) {
                    ans += height[j] >= minH ? 0 : minH - height[j];
                }

                // after calculation, reset the peaks and valleys

                valley = -1;

                // right peak peak2 can be the next water container's left peak
                peak1 = peak2;

                peak2 = -1;
            }
        }

        return ans;
    }
}

References