Problem
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.
Algorithm
At any location in A, the trapped water has a water level, i.e. the height of the water. The water level is determined by the left bar and the right bar, whichever is shorter. How to find the left bar and right bar for a given location ?
Left bar is the closest peak on its left side (wrong)
Counter Example
A = [5, 0, 2, 1, 5],
where the left bar of 1 is not 2, but 5.
Left bar is the highest bar on its left, and right bar is the highest bar on its right.
With this rule in mind, we can easily devise a O(n^3) algorithm. For each location in the array, scan left to find the highest bar on left, and scan right to find the highest bar on right. Then compute the water trapped at this location.
We can do better by scan from left to right, and store the highest left bar so far. At each location, scan the right highest bar. This algorithm only needs O(n^2) time.
We can do even better, using the "Double-Scan" Technique. Using two arrays lBar[i] and rBar[i] to store the highest left bar and highest right bar on i's left and right, not including i itself. The scan can be done in O(n). Then we can easily compute the water trapped with another iteration. So the total running time is O(n).
This technique was used in the problem Candy and the following problem.
Given an array of integers A, return another array B, where B[i] = the product of all elements except A[i]. You cannot use divide operator.
Using two helper arrays, leftProduct and rightProduct. Scan from left to right, compute the left product so far, excluding the ith element. Then scan from right to left, compute the right product so far. Finally, multiply the two arrays at each location, which is the product excluding A[i].
A = [5, 0, 2, 1, 5],
where the left bar of 1 is not 2, but 5.
Left bar is the highest bar on its left, and right bar is the highest bar on its right.
With this rule in mind, we can easily devise a O(n^3) algorithm. For each location in the array, scan left to find the highest bar on left, and scan right to find the highest bar on right. Then compute the water trapped at this location.
We can do better by scan from left to right, and store the highest left bar so far. At each location, scan the right highest bar. This algorithm only needs O(n^2) time.
We can do even better, using the "Double-Scan" Technique. Using two arrays lBar[i] and rBar[i] to store the highest left bar and highest right bar on i's left and right, not including i itself. The scan can be done in O(n). Then we can easily compute the water trapped with another iteration. So the total running time is O(n).
This technique was used in the problem Candy and the following problem.
Given an array of integers A, return another array B, where B[i] = the product of all elements except A[i]. You cannot use divide operator.
Using two helper arrays, leftProduct and rightProduct. Scan from left to right, compute the left product so far, excluding the ith element. Then scan from right to left, compute the right product so far. Finally, multiply the two arrays at each location, which is the product excluding A[i].
No comments:
Post a Comment