FastPrepTrapping Rain Water

Trapping Rain Water

Google logoGoogle● HardINTERNOA
Learn

Problem statement

You are given n non-negative integers representing an elevation map. Each bar has width 1.

Return how many units of rain water the elevation map can trap.

Function

trap(height: int[]) → int

Examples

Example 1

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

The bars trap a total of 6 units of water.

Example 2

height = [4,2,0,3,2,5]return = 9

The elevation map traps 9 units in total.

Example 3

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

A strictly increasing elevation map cannot trap water.

Constraints

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

More Google problems

See Google hiring insights
public int trap(int[] height) {
    // Write your code here.
}
height[0,1,0,2,1,0,1,3,2,1,2,1]
expected6
Checking account…