Katkat
Back

Measure Water Trapped Between Elevations

Hive.AiSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the ability to solve a classic dynamic programming/two-pointer challenge by calculating the volume of trapped water between bars of varying heights.

Problem Statement

Given an array heights representing an elevation map where the width of each bar is 1, compute how much rainwater you can trap after raining. The water level at any given index is limited by the minimum of the maximum heights to its left and right, minus the height of the bar at that index.

Function Signature

def trap(heights: List[int]) -> int:

Constraints

  • n == len(heights)
  • 0 <= n <= 10^5
  • 0 <= heights[i] <= 10^5

Examples

Example 1: Input: heights = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The elevation map is represented by [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water are being trapped.

Example 2: Input: heights = [4,2,0,3,2,5] Output: 9

Edge Cases

  • Empty input or arrays with fewer than 3 elements (cannot trap water).
  • Monotonically increasing or decreasing arrays (cannot trap water).
  • Arrays with large values or flat plateaus.

Hints

Hint 1

Consider that for any index `i`, the amount of water trapped is `min(max_left, max_right) - height[i]` if this value is positive.

Hint 2

Can you precompute the maximums to the left and right for every index to solve this in O(n) time and O(n) space?

Hint 3

To achieve O(1) space, use two pointers starting at the ends of the array, moving inward while keeping track of the current maximum height encountered from each side.

Follow-up questions

  • How would the solution change if the width of each bar were not 1, but provided as a separate array?
  • If you are restricted to O(1) extra space, explain why the two-pointer approach is mathematically sound even though you don't know the absolute maximum height on the 'other' side.
  • How would you adapt this algorithm for a 2D grid of elevations where water can flow in four directions?