Educatifu
Open menu

Trapping Rain Water

Hardarraystwo-pointers

Given an elevation map as bar heights, compute how much rain water is trapped between the bars after it rains.

Input

Line 1: an integer n. Line 2: n non-negative integers, the bar heights.

Output

The total units of trapped water.

Examples

Example 1

Input
12
0 1 0 2 1 0 1 3 2 1 2 1
Output
6

The classic map traps 6 units.

Example 2

Input
6
4 2 0 3 2 5
Output
9

Traps 9 units.

Example 3

Input
3
1 2 3
Output
0

Strictly increasing — nothing is trapped.

Constraints

  • 1 <= n <= 10^5
  • 0 <= each height <= 10^4

Hints

Reveal hint 1

Water above a bar is limited by the shorter of the tallest bar to its left and the tallest to its right.

Reveal hint 2

Two pointers from both ends, tracking the running left-max and right-max, computes this in one pass.

Reference solution (spoiler — try it yourself first)

Approach

Two pointers with running leftMax/rightMax. Advance from the side with the smaller current height, adding (max on that side − current height) as trapped water.

import sys
d = list(map(int, sys.stdin.read().split()))
n = d[0]
h = d[1:1 + n]
lo, hi = 0, n - 1
lm, rm, water = 0, 0, 0
while lo < hi:
    if h[lo] < h[hi]:
        if h[lo] >= lm:
            lm = h[lo]
        else:
            water += lm - h[lo]
        lo += 1
    else:
        if h[hi] >= rm:
            rm = h[hi]
        else:
            water += rm - h[hi]
        hi -= 1
print(water)

← All practice problems

Bring us the problem, not a perfect specification

Tell us what needs to change, who it affects and any important deadline. We will review the context and reply with useful next questions.

  1. 01Share contextDescribe the workflow, constraint or risk.
  2. 02Clarify togetherWe identify missing facts and useful options.
  3. 03Choose a startAgree a focused assessment or delivery step.
Start a conversation