Trapping Rain Water

Python data engineering interview problem. Difficulty: intermediate. Pattern: Two Pointers. About 10 minutes. Part of the Pro drill bank.

How much rainwater can be trapped between bars. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

A row of bars can leave valleys where rain collects. Water at one position is limited by the tallest bar to its left and the tallest bar to its right. Return the total number of water units trapped between the bars. Water cannot sit outside the first and last useful walls, and a low bar contributes only the gap between its height and the smaller boundary. Write the function trap_rain_water(height: list) -> int. For [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], the small valleys together hold 6 units. The starter file already has the function name and the harness print lines. Keep them, and fill only the function body.

Requirements

• For each valley, use the smaller of the best left and right boundaries.
• Do not count water below a bar or outside the ends.
• Return the total trapped amount as an integer.

Constraints

• height contains non-negative integers and may be unsorted.
• The return type is int; an empty or very short row cannot trap water.

Examples

Input: trap_rain_water([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) Output: 6 Water pools in the valleys.

Topics: lakebench, python, water, two pointers.

More Python interview questions · All interview problems · Learn data engineering