InternDoor

Rain caught between bars

Hardarrays · two pointers · stack

Reported in interviews at (where)

height[i] is the height of a bar 1 unit wide, and the bars stand side by side with no gaps. After heavy rain, water rests on top of a bar wherever taller bars on both its left and its right hold it in.

Return how many units of water stay, in total.

Example 1
Input
height = [3,0,2,0,4]
Output
7

The water rises to 3, the lower of the two end bars, so the middle bars hold 3, 1 and 3.

Example 2
Input
height = [2,5,1,1,3,0,1]
Output
5

Between 5 and 3 the two 1s hold 2 each, and the 0 between 3 and 1 holds 1.

Example 3
Input
height = [4,4]
Output
0

No bar has taller bars on both sides.

Limits

  • 1 <= height.length <= 100000
  • 0 <= height[i] <= 100000

Hints

Hint 1

Over bar i the water reaches the lower of the tallest bar on its left and the tallest bar on its right.

Hint 2

Walk two pointers inwards and always move the one on the lower side: that side's tallest bar so far decides the water there.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.