Quick 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.

Total Rainwater Held Between Bars of an Elevation Map

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Each element of `heights` is the height of a vertical bar of width 1, and the bars stand side by side with no gaps between them. After it rains, water collects in the dips between taller bars. Return the total amount of water the bars hold. ### Function Signature ```python def trapped_water(heights: list[int]) -> int: ``` ### Rules - `heights[i]` is the height of bar `i`; a height of 0 means there is no bar at that position, only ground. - Treat the bars as a two-dimensional cross-section. Water stays wherever it is walled in by bars on its left and on its right, with the ground below it. Water that is not walled in on both sides runs off the ends of the array. - Return the total trapped water in square units, one unit per 1 by 1 cell of water. ### 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 **Example 1** ```text Input: heights = [3, 0, 2, 0, 4] Output: 7 ``` ```text # #~~~# #~#~# #~#~# ``` `#` is a bar and `~` is water. The water stands at height 3 between the bar of height 3 and the bar of height 4: 3 units above index 1, 1 above index 2 and 3 above index 3. **Example 2** ```text Input: heights = [5, 4, 1, 2] Output: 1 ``` One unit sits above the bar of height 1, walled in by the bar of height 4 on its left and the bar of height 2 on its right. Any higher water would run off the right end. **Example 3** ```text Input: heights = [1, 2, 3] Output: 0 ``` Every bar is taller than the one before it, so no position is walled in on its left and all the water runs off the left end.

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.

Each element of `heights` is the height of a vertical bar of width 1, and the bars stand side by side with no gaps between them. After it rains, water collects in the dips between taller bars. Return the total amount of water the bars hold. ### Rules - `heights[i]` is the height of bar `i`; a height of 0 means there is no bar at that position, only ground. - Treat the bars as a two-dimensional cross-section. Water stays wherever it is walled in by bars on its left and on its right, with the ground below it. Water that is not walled in on both sides runs off the ends of the array. - Return the total trapped water in square units, one unit per 1 by 1 cell of water. ### 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; no value exceeds 2^31 - 1, so Java and C++ return `int`. ### Examples **Example 1** ```text Input: heights = [3, 0, 2, 0, 4] Output: 7 ``` ```text # #~~~# #~#~# #~#~# ``` `#` is a bar and `~` is water. The water stands at height 3 between the bar of height 3 and the bar of height 4: 3 units above index 1, 1 above index 2 and 3 above index 3. **Example 2** ```text Input: heights = [5, 4, 1, 2] Output: 1 ``` One unit sits above the bar of height 1, walled in by the bar of height 4 on its left and the bar of height 2 on its right. Any higher water would run off the right end.

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

  1. Look at one position at a time: how high can water stand above it before it would spill over a bar on one side?
  2. 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.
  3. A position with no taller bar somewhere on one of its sides, including either end of the array, holds nothing.

Rainwater Held Between Side-by-Side Bars

mediumBloombergSoftware Engineer

Each element of heights is the height of a vertical bar of width 1, and the bars stand side by side with no gaps between them. After it rains, water collects in the dips between taller bars. Return the total amount of water the bars hold.

Rules

  • heights[i] is the height of bar i; a height of 0 means there is no bar at that position, only ground.
  • Treat the bars as a two-dimensional cross-section. Water stays wherever it is walled in by bars on its left and on its right, with the ground below it. Water that is not walled in on both sides runs off the ends of the array.
  • Return the total trapped water in square units, one unit per 1 by 1 cell of water.

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; no value exceeds 2^31 - 1, so Java and C++ return int.

Examples

Example 1

Input:  heights = [3, 0, 2, 0, 4]
Output: 7
    #
#~~~#
#~#~#
#~#~#

# is a bar and ~ is water. The water stands at height 3 between the bar of height 3 and the bar of height 4: 3 units above index 1, 1 above index 2 and 3 above index 3.

Example 2

Input:  heights = [5, 4, 1, 2]
Output: 1

One unit sits above the bar of height 1, walled in by the bar of height 4 on its left and the bar of height 2 on its right. Any higher water would run off the right end.

Examples

Example 1
Input
([3, 0, 2, 0, 4],)
Output
7
Notes
Source example 1: water level 3 holds 3 + 1 + 3 units over indices 1 to 3.
Example 2
Input
([5, 4, 1, 2],)
Output
1
Notes
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.

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.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def trapped_water(heights: list[int]) -> int:
Sample call
trapped_water([3, 0, 2, 0, 4])
Language
Case 1
Input
([3, 0, 2, 0, 4],)
Expected
7
Case 2
Input
([5, 4, 1, 2],)
Expected
1

Browse More Questions

Show the approach

Approach

Water above index i can rise to level min(L(i), R(i)), where L(i) is the tallest bar in heights[0..i] and R(i) is the tallest bar in heights[i..n-1]; position i holds min(L(i), R(i)) - heights[i] units, and the answer is the sum over every index. Two pointers compute this in one pass with constant extra memory. Start with left = 0, right = n - 1, leftMax = rightMax = 0 and total = 0. While left < right: if heights[left] <= heights[right], settle index left (if heights[left] >= leftMax it becomes the new leftMax and holds nothing, otherwise it holds leftMax - heights[left]) and advance left; otherwise settle index right the same way against rightMax and move right inward. Invariant: the left pointer only leaves a bar that is no taller than the bar at the right pointer at that moment, and the right pointer only leaves a bar strictly shorter than the bar at the left pointer. Because the right pointer only moves inward, every bar the left pointer has passed is at most some bar in heights[right..n-1], and heights[left] <= heights[right], so when index left is settled L(left) <= R(left) and its level is exactly L(left) = max(leftMax, heights[left]); the symmetric argument gives level R(right) when index right is settled. The same invariant shows that the window [left, right] always still contains a tallest bar of the whole array, so the index where the pointers meet is a global maximum and holds no water; every other index is settled exactly once. Edge cases: a single bar skips the loop; with two bars the one settled end bar becomes its side maximum and holds nothing; all-zero, all-equal and monotone inputs return 0 because each settled bar is at least the running maximum on its side; positions at either end never hold water. The answer is at most 2 * 10^9, which fits a signed 32-bit integer; Java and C++ still accumulate in a 64-bit variable before returning int.

Time complexity:
O(n)
Space complexity:
O(1)