Trapping Rain Water

leetcode problem: 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.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

common problem analysis method

Inspired by this Chinese blog, I list some generalized rules to solve a problem and help us thinking. I will try to use those rules to analyze this problem.

• generalize condition: abstraction can let us skim the detail of problem and focus on main obstacle. More than that, abstraction can also help us draw conclusion/common solution from this kind of problems
• make condition more accurate: use some special case to inspire us how to solve it
• induce from result: the result may contains some more conditions to help us
• similar problem: the solution, the process to solve a similar problem may provide us some clues to solve this one
• adjust the conditions of problem( delete a condition, add a condition, change requirement): by this way, we can feel the inner connection between conditions, and how we can use them.
• divide and conquer

analysis process

Essence under description

What makes a hallow to trap some rain?

The first important question we have to think about is what makes a hallow to trap some rain? What this conclusion is ask us to do can be seen as summing all rain in every single hallow( induce from result; divide and conquer).

• First thought – climb up, climb down

int now = height[nowI], next = height[nextI];
if (now > next) {
    // start found, remember
} else if (now < next) {// end found
    rain += collect(start, end);
}

But using this way can cause many fake start point(s2) and fake end point(e2) as the following shows:

 s1             e1
____           ____  
    |s2     e2 | 
    ----   ---- 
       |   |
       -----

• start and end is higher
  Aware of the above the example, we should understand our hallow should be the longest possible sub-array, which make start and end higher than( have to be >) any point in the [start, end).

----     ----
    |   |
    -----

how to decide a hallow

Next problem is how computer can decide the start and end index? Computer can’t just see here is higher and there is lower. It can only scan the array. In the above example, we can also see that the end can decide the start: the end is higher, we may find a new start point to fit it. So the pseudo-code should be:

if (now < next) { // meet a possible end
    // find a start -- back trace
    // sum some rain
}

Similar problem

Analysis goes into this point, we come up with a similar problem: longest paren problem

Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
For “(()”, the longest valid parentheses substring is “()”, which has length = 2.
Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

In paren problem, we are going to find longest sub-array that start with ‘(’ and end with ‘)’, and the number of ‘(’ in [start, x) must large or equal to that of ‘)’. And if we find a ‘)’, we may find a paired ‘(’ by back-trace. Doesn’t this description sounds familiar?

go down <--> '('
go up <--> ')'
find start index to extend hallow <--> find '(' to extend paired paren

So we may learn some thought/details from the previous solution.

Solution

Finally, it’s the detail of solution, which is the extension of previous pseudo-code. What we should notice is how to find start index when meet an end.
Though above discussion, we can see the following fact:

• start is in [0, end - 1)
• if height[start] < height[end], height[start] must be the highest in [0, end); otherwise, we may find a higher start
• if x is in [0, end - 1), height[x] >= height[end], we are done: x is start.

We can easily turn above description into a linear back-trace code to finish this problem like following:

// return start index or -1 if no start available
int findStartSimple(vector<int>& height, int h, int i) {
    int max = 0;
    int mI = -1;
    for(int j = i - 1; j >= 0; j--) {
        if(height[j] >= h) {
            return j;
        }
        if(max < height[j]) {
            max = height[j];
            mI = j;
        }
    }
    if(mI == i - 1) {
        mI = -1;
    }
    return mI;
}

---

Or we can solve it in another dimension: height.

We can find all index in [0, end), at which height is larger than or equal to end. Then find the max index, if exist, which will be start. If all point in [0, end) are shorter than end, we just find the max.

int findStartMap(map<int, vector<int>>& h2i, int h, int i) {
    // try to find larger one first
    auto sameOrLarger = h2i.lower_bound(h);
    auto tmp = sameOrLarger;
    auto less = --tmp;
    int maxI = -1;
    while(sameOrLarger != h2i.end()) {
        vector<int>& larger = sameOrLarger->second;
        // find a larger one that before it
        auto index = lower_bound(larger.begin(), larger.end(), i);
        if (index != larger.begin()) {
            int tmp = *(index - 1);
            if(tmp > maxI) {
                maxI = tmp;
            }
        }
        sameOrLarger++;
    }
    if(maxI != -1) {
        return maxI;
    }

    while(less != h2i.begin()) {
        vector<int>& smaller = less->second;
        auto index = lower_bound(smaller.begin(), smaller.end(), i);
        if (index != smaller.begin()) {
            int tmp = *(index - 1);
            if(tmp == i - 1) {
                return -1;
            } else {
                return tmp;
            }
        }
        less--;
    }
    return -1;
}

What should be noticed is map solution may not be faster. The simple back-trace solution pass the test of leetcode but the map solution failed with TLE.

Full source can be found here.

Written with StackEdit.