FastPrepWater Pooled on an Elevation Map
Problems/Water Pooled on an Elevation Map

Water Pooled on an Elevation Map

Expedia logoExpedia● HardINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: An entry dated February 23, 2021, for a software engineering intern role in India names this task among its interview questions, without saying which round asked it.

The entry gives only the name, with no input format, examples or limits. Here, the row has 1 to 20,000 bars, each 1 unit wide and 0 to 100,000 units tall. The answer is one number: the total units of water held.

Our version is about 85% the same as the reported question.

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[]) → int

Examples

Example 1

height = [3,0,1,0,2]return = 5

The 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 = 0

The 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 = 13

The 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 <= 20000
  • 0 <= 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)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int trap(int[] height) {
        // Write your code here.
    }
}
Checking account…