Trap Rain Water Problem
The following problem is taken from yet another coding challenges web site named LeetCode.
This is a fun problem to solve and to show a nice divide and conquer approach to its solution.
Lets see how we can solve this problem using the famous induction approach.
Our induction will be on the number of bars.
What are our induction base cases ? Obviously we must have at least 3 bars to be able to trap water: 2 edge bars and one in the middle of hieght >= 0.
that means that P(1) = P(2) = 0.
Induction hypothesis P(n < N) - We know how to find the the amount of trapped water for n < N bars.
P(N) = ?
How do we reduce our problem from N to n < N ? First, observe that the water will always be trapped by two edge bars such that all the bars between them are shorter than they are. We can use this observation to reduce our problem into smaller sub problems. Lets first find the highest bar that is between the two edge bars. Lets denote its index by i, where 0 < i < N. We can use this bar to split our problem into two parts: the first between 0 and i with solution p(i) and the second between i and N with solution P(N - i). According to the induction hypothesis, we know how to solve P(i) and P(N - i). Let their joint trapped water be T. Now comes the tricky part. if the i'th bar that we picked is higher than either the left most edge bar or the right most edge bar, than we are done and T is our final answer. However, it could be that it is shorter than the left most edge bar (index 0) or from the right most edge bar (index N - 1). In this case the i'th bar will be itself trapped in water. In this scenario, how do we calculate the correct trapped water ? let j be the index of the shorter bar between the left and right bars. J contributes Hj - Hi to all the bars between it the the other edge bar. so the final result is actually T + ((Hj - Hi)* (N - 2). The reason for N - 2 is that we only count the bars between the two edge bars.
Lets see the code now:
In the first part, we find the index of the highest bar in between the two edge bars. We then split the problem into two sub problems and solve them recursively. After we get the joint solution for both (saved in variable Trapped) we check to see if any of the edge bars (left or right) are longer then the highest bar in between them, and perform the calculation as was described above. What is the run time of this algorithm ? Notice that the sub problems are not overlapping, so we never perform the same calculation more than once. Let R(i,j) be the runtime of the algorithms for bars i through j. We can see that R(i,j) = R(i,k) + R(k,j) for the index k of the highest bar between i and j. Also, R(i,i) = R(i,i+1) = R(j-1,j) = R(j,j) = O(1). In addition, the calculations we do after we return from the recursions are O(1). hence the total run time is O(N).
On a personal note, I would like to say that this was perhaps one of the more difficult problems to formulate in terms of induction. However, once I was able to formulate it properly, from the induction hypothesis to the algorithm the road was short. I hope you enjoyed it as much as I did.