Trapping Rain Water
Hard · Arrays & Strings · about 30 minutes
Asked at Amazon, Apple, Bloomberg, ByteDance, Figma, Google, Asana, Notion, Airtable.
Each value in height is the height of a bar of width 1, and the bars stand side by side. After a heavy rain, water collects in the dips between taller bars. Compute the total units of water held.