DevHireLab
TutorialsBootcamp
ProblemsCode SimulatorAI InterviewSoonContact
DevHireLab
TutorialsBootcamp
ProblemsCode SimulatorAI InterviewSoonContact
Back to Arena
hard
Array

Trapping Rain Water

**Problem Statement:** Given `n` non-negative integers representing an elevation map where the width of each bar is `1`, compute how much water it can trap after raining. **Hint / Expected Approach:** Two-pointer or prefix max arrays **Edge Cases to Consider:** - (1) All same height (no water) - (2) Monotonically increasing/decreasing - (3) Single or two bars

Examples

Example 1
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Example 2
Input: [4,2,0,3,2,5]
Output: 9
Example 3
Input: []
Output: 0

Constraints

  • ▪1 <= nums.length <= 10^4
  • ▪-10^9 <= nums[i] <= 10^9
  • ▪Time complexity should be O(n) or O(n log n)

Watch Out For Edge Cases

  • ▪All same height (no water)
  • ▪Monotonically increasing/decreasing
  • ▪Single or two bars
Frequently Asked At
GoogleAmazonMicrosoftMetaAdobeUberFlipkart