Total Rainwater Held Between Bars of an Elevation Map
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Overview: An array coding question: given the heights of adjacent bars of width one, compute the total amount of rainwater the bars hold after rain. It tests reasoning about how the bars on both sides bound the water above each position, and turning that into an efficient solution with little extra memory.
Constraints
- 1 <= len(heights) <= 2 * 10^4
- 0 <= heights[i] <= 10^5
- The answer is at most 2 * 10^9, which fits in a signed 32-bit integer.
Examples
Input: ([3, 0, 2, 0, 4],)
Expected Output: 7
Explanation: Source example 1: water level 3 holds 3 + 1 + 3 units over indices 1 to 3.
Input: ([5, 4, 1, 2],)
Expected Output: 1
Explanation: Source example 2: level is the lower right wall 2, so only 1 unit above the height-1 bar; a global-maximum level would overcount.
Hints
- Look at one position at a time: how high can water stand above it before it would spill over a bar on one side?
- The water above a position is limited by the lower of the walls that bound it on its left and on its right, as in Example 2.
- A position with no taller bar somewhere on one of its sides, including either end of the array, holds nothing.