Given an array of non-negative integers representing an elevation map where each element is the width of a bar of height equal to its value, calculate how much water can be trapped after raining.
For example, given height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], the output is 6 units of water.
Explain your approach, walk through the logic for determining water at each position, and analyze time and space complexity. Discuss at least two different approaches.
How to approach it
- Hint 1
The water above any bar is determined by the minimum of the tallest bar to its left and the tallest bar to its right, minus the bar's own height.
- Hint 2
Precomputing the max height to the left and right of each position lets you calculate water at each position independently.
- Hint 3
A two-pointer approach can avoid the extra arrays by tracking running maximums from both ends simultaneously.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.