Trapping Rain Water
Trapping Rain Water is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the In-place Array Modification subpattern.
Problem statement
The array height describes adjacent vertical bars. Bar i has a width of 1 and a height equal to height[i]; all bars share the same baseline, and water may remain only between bars that bound it.
For each position, determine how much water can be held above that bar after considering the tallest bar somewhere to its left and the tallest bar somewhere to its right. Water at the ends, where one side is missing, is zero.
Return the total number of unit squares of trapped water as an integer. Do not alter the required method signature.
Example 1:
Input: height = [3,0,2,0,4] Output: 7 Explanation: The two outer bars and the interior bars create water amounts of 3, 1, and 3 above the three low interior positions, for a total of 7.
Example 2:
Input: height = [2,0,2] Output: 2 Explanation: The middle position is enclosed by bars of height 2, so it holds 2 units of water.
Example 3:
Input: height = [1,3,0,2,1,4] Output: 6 Explanation: The positions between the bars of heights 3 and 4 hold 3, 1, and 2 units respectively, totaling 6.
Constraints:
- 1 <= height.length <= 2 10^4 - 0 <= height[i] <= 10^5 - Every element of height is an integer - Each bar has width 1 and rests on the same horizontal baseline
Topics and companies
Topics: Array, Two Pointers, Pointers.
How to practise Trapping Rain Water on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Trapping Rain Water in the code editor, or read the Trapping Rain Water editorial for a worked solution with its approach and complexity analysis.
Where Trapping Rain Water sits in the DSA pattern sheet
- Two Pointers pattern guide
- In-place Array Modification subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Trapping Rain Water
Other problems that use the same In-place Array Modification and Two Pointers techniques:
- Intersection of Two Arrays — Easy, same subpattern
- Merge Strings Alternately — Easy, same subpattern
- Move Pieces to Obtain a String — Medium, same subpattern
- Move Zeroes — Easy, same subpattern
- Remove Duplicates from Sorted Array — Easy, same subpattern
- Remove Duplicates from Sorted Array II — Medium, same subpattern