Loading page…
Practice problem · hard
A city map app has a flood layer. It shows the buildings along one street as a row of towers. Each tower is one metre wide, and the heights are in metres.
After heavy rain, water pools in the gaps between towers. A gap holds water up to the lower of the tallest tower to its left and the tallest tower to its right. Water at the two ends of the street runs off. You are asked to compute the total volume of water that stays.
Write trapped_water(towers).
towers[i] is the height of the tower at metre i.i is the lower of two heights: the tallest tower at or before i, and the tallest tower at or after i. The water above the tower is that level minus towers[i].Input: towers = [3, 0, 2, 0, 4]
Output: 7Pointers lo and hi start at the ends. left_max and right_max are the tallest towers seen from each side. The pointer at the lower tower moves, because that side's level is already known.
| lo | hi | towers[lo] | towers[hi] | Side that moves | Level | Water added | Total |
|---|---|---|---|---|---|---|---|
| 0 | 4 | 3 | 4 | left | 3 | 0 | 0 |
| 1 | 4 | 0 | 4 | left | 3 | 3 | 3 |
| 2 | 4 | 2 | 4 | left | 3 | 1 | 4 |
| 3 | 4 | 0 | 4 | left | 3 | 3 | 7 |
After the last step lo is 4, the same as hi, and the walk ends.
Input: towers = [5, 4, 3, 2, 1]
Output: 0The heights only fall, so there is never a taller tower on the right to hold water in.
Input: towers = [100000, 0, 100000]
Output: 100000One gap of depth 100,000 between two towers of height 100,000.
1 ≤ towers.length ≤ 100,000 (buildings on one street)0 ≤ towers[i] ≤ 100,000 (heights in metres)For each tower, a direct solution looks at every tower to its left and right. That is about n × n comparisons: 10^10 at n = 100,000, about 100 seconds at 10^8 operations a second. A two-pointer walk takes 100,000 steps.
The total can reach about 10^5 × 10^5 = 10^10, which does not fit in a 32-bit integer. Use a 64-bit type (long in Java, long long in C++).
trapped_water · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.