LeetCode Q42: Trapping Rain Water (hard)

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!

Solution 1:

The solution is very straight forward once you understand what the question really ask about. We basically need to find the highest and 2nd highest bar between which water can be trapped. To find all pairs of highest and 2nd highest, we use recursion.

Solution 2:
My another code. One observation is given highest bar of the problem, it separates array to two parts. In left parts, heights of all bars that can hold water are in ascending order, and in right part, heights of all bars that can hold water are in descending order. So, we can finish problem in two passes

Solution 3:
Similar to solution2, but can be done in one pass. Using two pointers. Two pointers will meet at the highest bar.