Loading page…
Practice problem · medium
A depot yard has a row of flood barriers, one metre apart. Each barrier has its own height in centimetres.
Before a storm, a crew can seal the gap between two barriers with a tarp and fill it with rain to store as a buffer. The water can rise only to the height of the shorter barrier. You are asked to find the tank that holds the most water.
Write largest_tank(walls).
walls[i] is the height of the barrier at metre i.i < j. Its size is the shorter height times the distance j - i.Input: walls = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49Pointers lo and hi start at the two ends. At each step the tank is the shorter wall times hi - lo. The shorter wall then moves in.
| lo | hi | Shorter wall | Tank | best after | Move |
|---|---|---|---|---|---|
| 0 | 8 | 1 | 8 | 8 | lo is shorter: lo becomes 1 |
| 1 | 8 | 7 | 49 | 49 | hi is shorter: hi becomes 7 |
| 1 | 7 | 3 | 18 | 49 | hi is shorter: hi becomes 6 |
| 1 | 6 | 8 | 40 | 49 | equal walls: hi becomes 5 |
| 1 | 5 | 4 | 16 | 49 | hi is shorter: hi becomes 4 |
| 1 | 4 | 5 | 15 | 49 | hi is shorter: hi becomes 3 |
| 1 | 3 | 2 | 4 | 49 | hi is shorter: hi becomes 2 |
| 1 | 2 | 6 | 6 | 49 | hi is shorter: hi becomes 1, the walk ends |
The best tank is between metre 1 and metre 8: height 7, distance 7.
Input: walls = [4, 4]
Output: 4Only one tank exists: height 4 times distance 1.
Input: walls = [0, 5, 0]
Output: 0Every tank is bounded by a barrier of height 0, so every tank is empty.
2 ≤ walls.length ≤ 100,000 (barriers in one yard)0 ≤ walls[i] ≤ 10,000 (heights in centimetres)Checking every pair of barriers costs about n × n ÷ 2 pairs. At n = 100,000 that is 5 × 10^9, about 50 seconds at 10^8 operations a second. A walk that moves one pointer per step makes at most 100,000 steps.
The largest tank is at most 10,000 × 99,999, about 10^9. That fits in a 32-bit integer.
largest_tank · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.