Quick Overview

Given the heights of adjacent unit-width bars in an elevation profile, compute the total amount of rainwater that stays trapped between them after rain, with water spilling off both open ends. The coding problem tests reasoning about the bars that bound each position and handling up to 100,000 bars efficiently.

Total Rainwater Trapped Above an Elevation Profile of Unit-Width Bars

Company: Goldman Sachs

Role: Quantitative Researcher

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

An elevation profile is made of vertical bars of width 1 standing side by side on flat ground. After heavy rain, water collects in the dips between bars, and any water that is not held in place by taller bars on both sides runs off the ends of the profile. Given the bar heights from left to right, return the total amount of water that stays trapped, measured in unit squares. ### Function Signature ```python def trapped_water(heights: list[int]) -> int: ``` `heights[i]` is the height of the bar at position `i`, from left to right. ### Rules - Bar `i` has width 1 and height `heights[i]`. Bars stand next to each other with no gaps, and a height of 0 means bare ground at that position. - A unit square of water at position `i` and level `y` (the band between heights `y` and `y + 1`) stays trapped exactly when `heights[i] <= y`, some bar strictly taller than `y` stands to the left of `i`, and some bar strictly taller than `y` stands to the right of `i`. All other water runs off; there are no walls beyond the first and last bars. - Return the total number of trapped unit squares. ### Constraints - `1 <= len(heights) <= 10^5` - `0 <= heights[i] <= 10^5` - The answer can exceed `2^31 - 1` (it is below `10^10`). Python integers handle this. ### Examples **Example 1** ```text Input: heights = [3, 0, 2, 0, 4] Output: 7 ``` The water between the bar of height 3 and the bar of height 4 settles at level 3. Positions 1, 2 and 3 hold 3, 1 and 3 units. **Example 2** ```text Input: heights = [1, 2, 3, 2, 1] Output: 0 ``` No position has a taller bar on both sides, so all water runs off. **Example 3** ```text Input: heights = [2, 0, 2, 1, 0, 1, 3] Output: 6 ``` Position 1 holds 2 units between the two bars of height 2. Positions 3, 4 and 5 fill to level 2, between the bar of height 2 at position 2 and the bar of height 3 at position 6, holding 1, 2 and 1 units.

Overview: Given the heights of adjacent unit-width bars in an elevation profile, compute the total amount of rainwater that stays trapped between them after rain, with water spilling off both open ends. The coding problem tests reasoning about the bars that bound each position and handling up to 100,000 bars efficiently.

Read the full Goldman Sachs Quantitative Researcher interview experience this question came from

An elevation profile is made of vertical bars of width 1 standing side by side on flat ground. After heavy rain, water collects in the dips between bars, and any water that is not held in place by taller bars on both sides runs off the ends of the profile. Given the bar heights from left to right, return the total amount of water that stays trapped, measured in unit squares. Implement `trapped_water(heights)`, where `heights[i]` is the height of the bar at position `i`, from left to right. ### Rules - Bar `i` has width 1 and height `heights[i]`. Bars stand next to each other with no gaps, and a height of 0 means bare ground at that position. - A unit square of water at position `i` and level `y` (the band between heights `y` and `y + 1`) stays trapped exactly when `heights[i] <= y`, some bar strictly taller than `y` stands to the left of `i`, and some bar strictly taller than `y` stands to the right of `i`. All other water runs off; there are no walls beyond the first and last bars. - Return the total number of trapped unit squares as a single integer. ### Constraints - `1 <= len(heights) <= 10^5` - `0 <= heights[i] <= 10^5` - The answer can exceed `2^31 - 1` (it is below `10^10`), so it is returned as a 64-bit integer: `long` in Java and `long long` in C++. Python integers and JavaScript numbers hold it exactly. ### Examples **Example 1** ```text Input: heights = [3, 0, 2, 0, 4] Output: 7 ``` The water between the bar of height 3 and the bar of height 4 settles at level 3. Positions 1, 2 and 3 hold 3, 1 and 3 units. **Example 2** ```text Input: heights = [2, 0, 2, 1, 0, 1, 3] Output: 6 ``` Position 1 holds 2 units between the two bars of height 2. Positions 3, 4 and 5 fill to level 2, between the bar of height 2 at position 2 and the bar of height 3 at position 6, holding 1, 2 and 1 units.

Constraints

  • 1 <= len(heights) <= 10^5
  • 0 <= heights[i] <= 10^5
  • The answer can exceed 2^31 - 1 (it is below 10^10); return it as a 64-bit integer (long in Java, long long in C++).

Examples

Input: ([3, 0, 2, 0, 4],)

Expected Output: 7

Explanation: Source example 1: positions 1, 2 and 3 fill to level 3, holding 3, 1 and 3 units.

Input: ([1, 2, 3, 2, 1],)

Expected Output: 0

Explanation: Source example 2: single peak, no position has a taller bar on both sides, so all water runs off.

Hints

  1. Look at one position at a time: how many unit levels above it satisfy the trapping rule?
  2. Only the tallest bar strictly to the left and the tallest bar strictly to the right of a position decide how much water sits above it.
  3. With up to 10^5 bars, avoid rescanning the profile for every position, and keep the running total in a 64-bit integer.

Loading coding console...

Show the approach

Approach

Water above one position: by the rules, the unit square at position i and level y is trapped exactly when heights[i] <= y, y < L and y < R, where L is the tallest bar strictly left of i and R the tallest bar strictly right of i (0 when there is none). So position i holds max(0, min(L, R) - heights[i]) units, and the answer is the sum over all positions.

Two pointers compute this in one pass. left starts at 0 and right at n - 1; left_max is the tallest bar already passed on the left and right_max the tallest already passed on the right. Invariant: the taller of heights[left] and heights[right] is at least every bar already passed on either side, because only the shorter pointer (the right one on ties) ever moves inward. If heights[left] < heights[right], the true right maximum for position left is at least heights[right] >= left_max, so min(L, R) = left_max and the position holds max(0, left_max - heights[left]): add it, or raise left_max when the bar is at least as tall, then advance left. Otherwise the symmetric argument settles position right using right_max. Every position is settled once; the position where the pointers meet is a tallest bar overall and holds nothing.

Edge cases: a single bar or two bars hold no water; the first and last bars never add water because they become left_max or right_max before anything is added (there are no outer walls); flat, all-zero and monotone profiles give 0; an equal-height neighbour never traps water above its own top (strictly-taller rule). The total can approach 10^10, so it is accumulated in a 64-bit integer (long in Java, long long in C++).

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