12_trapping-rain-water.md

42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Difficulty:

Hard

Lock:

Normal

Company:

Adobe Affirm Airbnb Amazon Apple Atlassian Bloomberg ByteDance Citadel Databricks Dataminr Electronic Arts Facebook Flipkart Goldman Sachs Google Grab HBO Huawei Lyft Microsoft Nvidia Oracle Palantir Technologies Qualtrics Salesforce Snapchat Tableau Twitter Uber Visa Walmart Labs Wish Yahoo Yandex Zenefits Zoho