Leetcode 42: Trapping Rain Water

Feb. 2, 2018

Plan to work on hard level algorithm Leetcode 42.

May 23, 2018

I could not believe that I could not come out the idea to calculate the rain water when I was asked by the interviewer on May 22, 2018 8:30 PM. I asked one of Chinese graduate student to help me, give me some mock interviews and this was the first algorithm he asked me.

I talked about descending stack, and the interviewer asked me why it is the descending stack. And also the interviewer asked me to give out the correct brute force solution. I noticed that my brute force solution is also not correct. I need to find left boundary for the current bar which should be maximum height of prefix elements.

Here is my C# solution written after the mock interview.

There are three issues to fix in order to pass online judge. First one is to check base condition, check array length is 0 on line 26; second one is to apply Array.Reverse API, it has been called three times. And the last one is to add if condition statement on line 49.