Skip to content
Katabench
Try free

Trapping Rain Water

Hard About 30 min Free, no account needed

Compute how much rain water is trapped between bars of an elevation map.

The brief

Given height, an elevation map where each bar has width 1, return how much water is trapped after it rains. Water above bar i is bounded by the tallest bar to its left and the tallest to its right: min(maxLeft, maxRight) - height[i].

The performance bar

The obvious approach rescans for the left and right maxima at every bar, O(n²). The hidden test uses 200,000 bars, so it's too slow. Aim for Trap in O(n).

The total can exceed int.MaxValue, so the method returns a long.

Starter code

C#
using System;

public class Solution
{
    // TODO: return the total units of water trapped between the bars.
    public long Trap(int[] height)
    {
        throw new NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Two pointers
Walk a sorted or symmetric sequence from both ends, or fast and slow, instead of checking every pair.

Do these first

Related katas