Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Arrays

Trapping Rain Water

Hard · Arrays · Asked at Google, Amazon, Microsoft, Goldman Sachs, Adobe

Given bar heights, compute how much rain water is trapped between the bars after raining.

Input

First line: n. Second line: n space-separated integers.

Output

The total units of trapped water.

Constraints

Water above bar i = min(max height on the left, max height on the right) − h[i]. Two pointers make it O(1) space.

Example 1

Input

12
0 1 0 2 1 0 1 3 2 1 2 1

Output

6

Example 2

Input

6
4 2 0 3 2 5

Output

9

Hints

  1. Water above bar i = min(tallest bar on its left, tallest bar on its right) − h[i].
  2. Two pointers: always move the side with the smaller maximum — that side's water level is already known.

Approach

Prefix and suffix maximum arrays give an O(n)-space answer. The two-pointer version needs O(1) space. Keep l, r and the running maxima leftMax and rightMax. If leftMax <= rightMax, the water at l is limited by leftMax, since something at least that tall exists on the right. So add leftMax − h[l] and move l. Otherwise handle r symmetrically. The total can exceed 32 bits (10^5 × 10^5), so use 64 bits.

Complexity: O(n) time · O(1) extra space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> h(n);
    for (auto &x : h) cin >> x;
    int l = 0, r = n - 1;
    long long leftMax = 0, rightMax = 0, water = 0;
    while (l <= r) {
        leftMax = max(leftMax, h[l]);
        rightMax = max(rightMax, h[r]);
        if (leftMax <= rightMax) water += leftMax - h[l++];
        else water += rightMax - h[r--];
    }
    cout << water << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
h = data[1 : data[0] + 1]
l, r = 0, len(h) - 1
left_max = right_max = water = 0
while l <= r:
    left_max = max(left_max, h[l])
    right_max = max(right_max, h[r])
    if left_max <= right_max:
        water += left_max - h[l]
        l += 1
    else:
        water += right_max - h[r]
        r -= 1
print(water)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] h = new long[n];
        for (int i = 0; i < n; i++) h[i] = sc.nextLong();
        int l = 0, r = n - 1;
        long leftMax = 0, rightMax = 0, water = 0;
        while (l <= r) {
            leftMax = Math.max(leftMax, h[l]);
            rightMax = Math.max(rightMax, h[r]);
            if (leftMax <= rightMax) water += leftMax - h[l++];
            else water += rightMax - h[r--];
        }
        System.out.println(water);
    }
}

Solve Trapping Rain Water online · All practice problems