[Two Pointer] Trapping Rain Water

[sudosf]

Problem

Given an array of heights representing an elevation map, compute how much water can be trapped after rain.

References

• LeetCode: https://leetcode.com/problems/trapping-rain-water/
• GFG: https://www.geeksforgeeks.org/problems/trapping-rain-water-1587115621/1
• Sheet: https://www.risingbrain.org/sheet#array (Two Pointer [Two Pointer] 3Sum #6)
• Parent: Pattern: Two Pointers (Arrays) #3

Difficulty

🔴 Hard

Companies

Google, Goldman Sachs, Sumo Logic

Notes

Language: Java
Multiple approaches: O(n) space prefix arrays, or O(1) space two-pointer. Understand both.