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.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) 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.
Example 2:
Input: height = [4,2,0,3,2,5] Output: 9
Constraints:
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105The Trapping Rain Water problem asks you to compute how much water can be trapped between vertical bars after rainfall. The key insight is that the water level above any index depends on the maximum height to its left and right. The trapped water at a position is limited by the smaller of these two boundaries.
A common strategy is to precompute left_max and right_max arrays using dynamic programming, allowing you to determine the water stored at each position efficiently. Another more space‑efficient method uses the two pointers technique, where pointers move inward from both ends while maintaining current maximum boundaries. This approach avoids extra arrays and processes the elevation map in a single pass.
Alternatively, a monotonic stack can be used to identify bounded regions where water accumulates by tracking decreasing height indices. While multiple approaches exist, the two‑pointer technique is typically preferred due to its O(n) time and O(1) extra space complexity.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers | O(n) | O(1) |
| Dynamic Programming (Left/Right Max Arrays) | O(n) | O(n) |
| Monotonic Stack | O(n) | O(n) |
NeetCode
This approach involves creating two auxiliary arrays to store the maximum heights on the left and right of each bar. With these arrays, you can calculate how much water each bar can trap.
The water trapped above a bar is determined by the minimum of the maximum heights on its left and right, minus the bar's height itself.
Time Complexity: O(n) because we traverse the height array three times where n is the length of the array.
Space Complexity: O(n) due to the additional arrays used to store the maximum heights.
1#include <stdio.h>
2#include <stdlib.h>
3
4int trap(int* height, int heightSize) {
5 if (
This implementation uses two arrays: leftMax and rightMax to keep track of the maximum height encountered from the left and right of each bar respectively. It then calculates the trapped water by iterating through each bar and adding the minimum of these maximum heights minus the bar's height.
The two-pointer technique optimizes space by keeping track of the left and right bars with two pointers. It uses a single loop and calculates water based on the shorter of the two heights at the current pointers.
Time Complexity: O(n), where n is the length of the input array since we process each bar only once.
Space Complexity: O(1) because we use only constant extra space.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Trapping Rain Water is a well-known hard-level interview problem frequently asked in FAANG and other top tech companies. It tests understanding of arrays, two pointers, stacks, and problem-solving intuition.
The optimal approach is the two pointers technique. By tracking the maximum height from both ends and moving the pointer with the smaller boundary, you can compute trapped water in a single pass with O(n) time and O(1) extra space.
Several approaches use different structures. A monotonic stack can track indices of bars to find bounded regions, while dynamic programming uses auxiliary arrays for left and right maximum heights.
Water trapped at any position depends on the shorter boundary between the highest bar on the left and the highest bar on the right. Calculating these boundaries helps determine the maximum possible water level at each index.
This approach leverages two pointers, starting from both ends of the array and moving towards the center. It dynamically updates the maximum height seen so far from either direction and calculates water trapped at the current position based on these max heights.