You’re interviewing for a backend or data engineering role at a FAANG-level company. The interviewer describes a real product scenario:
A large-scale infrastructure monitoring team models burst traffic across a distributed system as a skyline. Each node has a capacity limit, and when traffic spikes, unused capacity in lower nodes gets temporarily buffered between higher-capacity nodes, similar to water collecting between walls.
The skyline is represented by an integer array height, where each value is the capacity limit at that position. After a heavy traffic spike, the system wants to estimate how much total buffered capacity was held across the entire line.
This is a common coding interview and DSA question might ask in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.
Your Task
Given an integer array height representing a skyline, return the total amount of trapped water after raining.
Water at index i depends on the tallest barrier to the left and to the right:
water[i] = min(max_left[i], max_right[i]) - height[i] if positive
Input Format
height: an array of integers representing wall heights
Output Format
- A single integer representing the total trapped rain water
Examples
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The skyline traps 6 units of water in total.
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9