Water Pooled on an Elevation Map
Updated
Problem statement
You are given an array height. It describes a row of bars standing side by side with no gaps: bar i is 1 unit wide and height[i] units tall. A bar of height 0 is an empty spot on the ground.
Rain falls on the bars. Water can stay above a spot only if there is a taller bar somewhere on its left and somewhere on its right to hold it in; any water that is not walled in on both sides runs off the ends of the row.
Return the total number of units of water that stay on top of the bars once the rain stops.
Function
trap(height: int[]) → intExamples
Example 1
height = [3,0,1,0,2]return = 5The water level is set by the lower of the two walls, 3 and 2, so it is 2. Above the bars 0, 1 and 0 the water is 2, 1 and 2 units deep. The total is 2 + 1 + 2 = 5.
Example 2
height = [2,3,3,7,8]return = 0The heights never go down from left to right, so no bar has a taller bar on its left. Water runs off to the left and nothing is held.
Example 3
height = [5,1,4,0,2,6,3]return = 13The bars 5 and 6 form the walls of one pool, so its level is 5. Above the bars 1, 4, 0 and 2 the water is 4, 1, 5 and 3 units deep, which adds up to 13. The last bar, 3, has no taller bar on its right, so no water stays on it.
Constraints
1 <= height.length <= 200000 <= height[i] <= 100000
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Trapping Rain WaterMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Trapping Rain WaterOracle · PHONE SCREENOracle interview questions
- Trapping Rain WaterGoogle · OAGoogle interview questions
- Rain Kept Between WallsDocuSign · PHONE SCREENDocuSign interview questions
- Rain Water Held Between BarsAdobe · PHONE SCREENAdobe interview questions
- Trapping Rain WaterBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Dungeon GameAmazon · ONSITE INTERVIEW
- Global Charger AssignmentSpotify · ONSITE INTERVIEW
- Minimum Taps to Water a GardenThe D.E. Shaw Group · ONSITE INTERVIEWThe D.E. Shaw Group interview questions
- Longest Increasing Path in a MatrixNew Relic · PHONE SCREEN · ONSITE INTERVIEW
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)