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 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 along.
Starter code
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.
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
- Boats to Save People Medium Free Pair people into two-person boats under a weight limit, using as few boats as possible.
- Find the Duplicate Number Medium Free Find the one repeated value in an array of n+1 numbers from 1..n, without allocating a set to do it.
- Longest Palindromic Substring (Length) Medium Free How long is the longest palindrome hiding in the string?
- Sort Colors Medium Free Sort an array of 0s, 1s and 2s in a single pass.