Trapping Rain Water
Updated
Problem statement
You are given an array height of non-negative integers. Bar i stands at position i, is 1 unit wide and height[i] units tall, and the bars stand side by side with no gaps.
After it rains, water collects between the bars. Above each bar, the water rises to the height of the shorter of two walls: the tallest bar at or to the left of it, and the tallest bar at or to the right of it. Water above the first or last bar has nothing to hold it on the outer side, so it runs off.
Return the total number of units of water that are trapped.
Function
trap(height: int[]) → intExamples
Example 1
height = [3,0,2,0,4]return = 7The lower of the two end walls has height 3. Above the bar of height 0 at index 1 the water rises to 3, above the bar of height 2 it rises 1 more unit, and above the bar of height 0 at index 3 it rises to 3. In total 3 + 1 + 3 = 7 units.
Example 2
height = [1,0,2,1,0,1,3]return = 5Index 1 holds 1 unit, because its walls are 1 and 3 and the lower one is 1. Indices 3, 4 and 5 sit between the walls 2 and 3, so the water there is 2 high: they hold 1, 2 and 1 units. In total 1 + 1 + 2 + 1 = 5 units.
Example 3
height = [1,2,3,2,1]return = 0The bars only go up and then down. No bar has a taller bar on both sides, so no water is trapped and the answer is 0.
Constraints
1 <= height.length <= 2 * 10^40 <= height[i] <= 10^5
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- 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
- 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 WaterRupeek · ONSITE INTERVIEW
- Water Pooled on an Elevation MapExpedia · ONSITE INTERVIEWExpedia interview questions
- Trapping Rain WaterOracle · PHONE SCREENOracle interview questions
Interview reports that mention this question
Microsoft interview experiences
- Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
- Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
- Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
- Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
- Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)