Trapping Rain Water
Updated
Problem statement
You are given n non-negative integers in height. They describe an elevation map: bar i has width 1 and height height[i], and the bars stand next to each other from left to right.
Rain falls on the map. For each bar i, look at the tallest bar from the start up to i and the tallest bar from i to the end. The water level above bar i is the lower of these two heights, so bar i holds that level minus height[i] units of water. Return how many units of water are trapped in total.
Function
trap(height: int[]) → intExamples
Example 1
height = [0,1,0,2,1,0,1,3,2,1,2,1]return = 6Water sits above index 2 (1 unit), indices 4, 5 and 6 (1 + 2 + 1 units) and index 9 (1 unit). The total is 6.
Example 2
height = [4,2,0,3,2,5]return = 9The walls are 4 on the left and 5 on the right, so the water level between them is 4. Index 1 holds 4 - 2 = 2, index 2 holds 4, index 3 holds 1 and index 4 holds 2, for a total of 9.
Example 3
height = [5,4,3,2,1]return = 0The bars only get lower to the right, so no bar has a wall on its right side. No water is trapped, and the answer is 0.
Constraints
n == height.length1 <= n <= 2 * 10^40 <= height[i] <= 10^5
More Teradata interview questions
Similar questions at other companies
- Trapping Rain WaterBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Trapping Rain WaterAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Trapping Rain WaterKotak Mahindra Bank · ONSITE INTERVIEWKotak Mahindra Bank interview questions
- Trapping Rain WaterNuro · ONSITE INTERVIEWNuro interview questions
- Trapping Rain WaterMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Trapping Rain WaterRupeek · ONSITE INTERVIEW
- Trapping Rain WaterGoogle · OAGoogle interview questions
- Rain Kept Between WallsDocuSign · PHONE SCREENDocuSign interview questions
- Rain Water Held Between BarsAdobe · PHONE SCREENAdobe interview questions
- Construct a Tree from Level-Order and Inorder TraversalsSalesforce · ONSITE INTERVIEWSalesforce interview questions