Calculate trapped water between elevation bars
Company: Tesla
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an array of non-negative integers representing the heights of unit-width vertical bars, compute the total water retained after rainfall. Start by presenting a brute-force approach and analyze its time and space complexity. Then optimize to a linear-time solution that uses constant extra space, explain the intuition, and implement the final method.
Quick Answer: This question evaluates array manipulation, algorithmic optimization, and complexity analysis, specifically the ability to reason about time and space trade-offs and design a linear-time, constant-space approach for computing trapped water.
Given an array of non-negative integers `height` representing the heights of unit-width vertical bars laid side by side, compute the total amount of water that is trapped after it rains.
Water collects in the dips between bars. For each position, the water held above it is bounded by the tallest bar to its left and the tallest bar to its right: the water level at that position is `min(maxLeft, maxRight)`, and the trapped water there is `min(maxLeft, maxRight) - height[i]` (never negative).
The interviewer first asks for a brute-force approach and its complexity, then asks you to optimize to a linear-time, constant-extra-space solution and explain the intuition.
Example:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Return the total units of trapped water.
Constraints
- 0 <= height.length <= 2 * 10^4
- 0 <= height[i] <= 10^5
- The array may be empty, in which case the answer is 0.
Examples
Input: ([0,1,0,2,1,0,1,3,2,1,2,1],)
Expected Output: 6
Explanation: The canonical LeetCode 42 example: 6 units of water collect in the valleys between the bars.
Input: ([4,2,0,3,2,5],)
Expected Output: 9
Explanation: Water is bounded by the height-4 bar on the left and the height-5 bar on the right; the dip holds 9 units.
Hints
- Brute force: for each index i, scan left and right to find the tallest bar on each side; the water above i is max(0, min(maxLeft, maxRight) - height[i]). This is O(n^2) time, O(1) space.
- Precomputing prefix-max-from-left and suffix-max-from-right arrays drops the per-index scan to O(1), giving O(n) time but O(n) extra space.
- To reach O(1) space, use two pointers from both ends. Track left_max and right_max as you move inward; always advance the side whose running max is smaller, because that side's water level is fully determined by it.
- When left_max <= right_max, the water at the left pointer depends only on left_max (right_max is at least as tall), so you can safely add left_max - height[left] and step left forward. Symmetric reasoning applies on the right.