Trapping Rain Water

📋

Problem

Imagine a city skyline after a heavy rainstorm, where water collects between buildings of different heights. How much water is trapped between these buildings?

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. Input: An array of integers height[] representing the elevation map. Output: An integer representing total units of trapped rain water.

1 ≤ n ≤ 10^50 ≤ height[i] ≤ 10^5

Edge cases: All bars of same height → 0 trapped waterStrictly increasing heights → 0 trapped waterStrictly decreasing heights → 0 trapped water

</>

IDE

def trap(height: list[int]) -> int:public int trap(int[] height)int trap(vector<int> &height)function trap(height)

def trap(height):
    # Write your solution here
    pass

class Solution {
    public int trap(int[] height) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int trap(vector<int> &height) {
    // Write your solution here
    return 0;
}

function trap(height) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning zero for all inputs due to missing trapped water calculation logic.✅ Implement min(left_max, right_max) - height[i] calculation for each index and sum results.

Wrong: Incorrect sum less than expectedUsing greedy approach that only considers local maxima or only one side's max height.✅ Use two-pointer or prefix/suffix max arrays to consider both left and right max heights for each index.

Wrong: IndexError or crashNot handling empty input or single element arrays properly.✅ Add checks for empty or very small arrays and return 0 immediately.

Wrong: Negative trapped water values summedNot using max(0, min(left_max, right_max) - height[i]) causing negative contributions.✅ Ensure trapped water at each index is max(0, min(left_max, right_max) - height[i]).

Wrong: Timeout (TLE)Using brute force O(n^2) nested loops approach for large inputs.✅ Implement O(n) two-pointer or prefix/suffix max arrays approach.

✓

Test Cases

Review base cases and ensure your code handles empty and single-element arrays correctly.

Focus on algorithmic correctness; avoid greedy traps and off-by-one errors.

Optimize your solution to linear time using two-pointer or prefix/suffix max arrays.

t1_01basic

Input{"height":[0,1,0,2,1,0,1,3,2,1,2,1]}

Expected6

⏱ Performance - must finish in 2000ms

Water trapped at indices 2,4,5,6,9,10 sums to 6 units.

💡 Consider the maximum height to the left and right of each bar.

💡 Use prefix max and suffix max arrays to find trapped water at each index.

💡 Water trapped at i = min(prefix_max[i], suffix_max[i]) - height[i], sum over all i.

Why it failed: Incorrect total trapped water. Likely missing min(left_max, right_max) logic or incorrect indexing. Fix by computing prefix and suffix max arrays correctly and summing min of these minus height.

✓ Correctly computes total trapped water using prefix and suffix max arrays.

t1_02basic

Input{"height":[4,2,0,3,2,5]}

Expected9

⏱ Performance - must finish in 2000ms

Water trapped at indices 1,2,3,4 sums to 9 units.

💡 Check water trapped at each index by comparing left and right max heights.

💡 Remember to handle valleys where height is lower than both sides.

💡 Sum min(left_max, right_max) - height[i] for all i to get total trapped water.

Why it failed: Wrong trapped water sum. Possibly not considering both sides' max heights or off-by-one errors. Fix by ensuring min(left_max, right_max) is used for each index.

✓ Correctly calculates trapped water for varied height array.

t2_01edge

Input{"height":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty array means no bars, so no trapped water.

💡 Check how your code handles empty input arrays.

💡 Ensure no index errors occur when n=0.

💡 Return 0 immediately if input is empty.

Why it failed: Fails on empty input due to index errors or no base case. Fix by adding a check for empty array and returning 0.

✓ Handles empty input gracefully, returning 0.

t2_02edge

Input{"height":[5]}

Expected0

⏱ Performance - must finish in 2000ms

Single bar cannot trap any water.

💡 Consider the minimum number of bars needed to trap water.

💡 For single element, trapped water is always zero.

💡 Return 0 if array length is less than 2.

Why it failed: Incorrect trapped water for single bar, likely missing base case for n=1. Fix by returning 0 if length < 2.

✓ Correctly returns 0 for single bar input.

t2_03edge

Input{"height":[1,1,1,1,1]}

Expected0

⏱ Performance - must finish in 2000ms

All bars same height, no space to trap water.

💡 Check if your code handles flat surfaces correctly.

💡 Water trapped depends on difference between bar height and min of max heights.

💡 If all heights equal, trapped water is zero.

Why it failed: Fails to return zero for uniform height bars, possibly summing negative or positive values incorrectly. Fix by ensuring trapped water at each index is max(0, min(left_max, right_max) - height[i]).

✓ Correctly returns 0 for uniform height bars.

t3_01corner

Input{"height":[5,4,1,2]}

Expected1

⏱ Performance - must finish in 2000ms

Water trapped only at index 2 with 1 unit.

💡 Beware of greedy approaches that only look at local maxima.

💡 Check both left and right max heights for each index.

💡 Use two-pointer approach or prefix/suffix max arrays to avoid greedy traps.

Why it failed: Greedy approach fails by not considering right max heights properly, resulting in over or under counting. Fix by using two-pointer or prefix/suffix max arrays to consider both sides.

✓ Correctly handles cases where greedy approach fails.

t3_02corner

Input{"height":[0,1,0,1,0,1,0,1]}

Expected3

⏱ Performance - must finish in 2000ms

Water trapped at indices 2,4,6 each 1 unit, total 3.

💡 Check for off-by-one errors in loops or indexing.

💡 Ensure all indices are considered and boundaries handled correctly.

💡 Verify that trapped water calculation uses correct indices and min of max heights.

Why it failed: Off-by-one error causes missed trapped water at some indices. Fix by carefully iterating over all indices and correctly computing min(left_max, right_max) - height[i].

✓ Correctly computes trapped water with proper indexing.

t3_03corner

Input{"height":[2,0,2,0,2]}

Expected4

⏱ Performance - must finish in 2000ms

Water trapped at indices 1 and 3 with 2 units each, total 4.

💡 Avoid confusing 0/1 knapsack style logic with this problem.

💡 Focus on min of max heights on both sides, not cumulative sums.

💡 Use two-pointer approach to track left_max and right_max dynamically.

Why it failed: Confusing problem with knapsack leads to incorrect accumulation logic. Fix by using min(left_max, right_max) - height[i] for each index, not cumulative sums.

✓ Correctly applies trapping water logic distinct from knapsack.

t4_01performance

Input{"height":[100000,99999,99998,99997,99996,99995,99994,99993,99992,99991,99990,99989,99988,99987,99986,99985,99984,99983,99982,99981,99980,99979,99978,99977,99976,99975,99974,99973,99972,99971,99970,99969,99968,99967,99966,99965,99964,99963,99962,99961,99960,99959,99958,99957,99956,99955,99954,99953,99952,99951,99950,99949,99948,99947,99946,99945,99944,99943,99942,99941,99940,99939,99938,99937,99936,99935,99934,99933,99932,99931,99930,99929,99928,99927,99926,99925,99924,99923,99922,99921,99920,99919,99918,99917,99916,99915,99914,99913,99912,99911,99910,99909,99908,99907,99906,99905,99904,99903,99902,99901]}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100, strictly decreasing heights, O(n) solution must complete within 2 seconds.

💡 Brute force O(n^2) will time out for n=100.

💡 Use two-pointer or prefix/suffix max arrays for O(n) time.

💡 Optimize to O(n) time and O(1) or O(n) space to pass.

Why it failed: TLE due to O(n^2) brute force approach. Fix by implementing O(n) two-pointer or prefix/suffix max approach.

✓ Solution runs in O(n) time confirming optimal complexity.

Practice

1. Consider the following Python code implementing the bottom-up DP solution for the Burst Balloons problem. What is the final returned value when the input is [3,1,5,8]?

def maxCoins(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for left in range(n - length):
            right = left + length
            for i in range(left + 1, right):
                coins = nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]
                dp[left][right] = max(dp[left][right], coins)
    return dp[0][n - 1]

print(maxCoins([3,1,5,8]))

easy

A. 167

B. 144

C. 120

D. 135

Solution

1. Step 1: Trace dp array initialization and boundaries

   Input is extended to [1,3,1,5,8,1]. dp is a 6x6 matrix initialized to 0.

2. Step 2: Compute dp values for increasing subarray lengths

   By iterating length from 2 to 5, dp[0][5] accumulates the maximum coins by considering all bursting orders. The known optimal result for [3,1,5,8] is 167 coins.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches known example output [OK]

Hint: Known example output is 167 coins [OK]

Common Mistakes:

• Off-by-one in indices
• Forgetting to add virtual balloons
• Miscomputing dp updates

2. You are given a list of envelopes, each with a width and height. You want to find the maximum number of envelopes you can nest inside each other such that each envelope fits strictly inside the next one by both width and height. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach by sorting envelopes by width and picking the tallest envelope at each step.

B. Sort envelopes by width ascending and height descending, then find the Longest Increasing Subsequence (LIS) on heights using binary search.

C. Dynamic programming with a 2D table tracking all pairs of envelopes to find the longest chain.

D. Use a graph and find the longest path by topological sorting.

Solution

1. Step 1: Understand problem constraints

   The problem requires strict increasing order in both width and height for nesting envelopes.

2. Step 2: Identify optimal approach

   Sorting by width ascending and height descending ensures envelopes with the same width do not interfere. Then LIS on heights finds the longest chain efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + LIS with binary search is the known optimal approach [OK]

Hint: Sort width asc, height desc, then LIS on heights [OK]

Common Mistakes:

• Using greedy picking tallest envelope only
• Applying LIS on widths instead of heights
• Using DP without sorting properly

3. You are given k sorted lists of integers. Your task is to find the smallest range that includes at least one number from each of the k lists. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Use a greedy approach that always picks the smallest current element and expands the range until all lists are covered.

B. Merge all lists into one sorted array with list indices, then use a two-pointer sliding window to find the minimal range covering all lists.

C. Apply dynamic programming to track the minimal range for subsets of lists incrementally.

D. Enumerate all possible combinations of elements from each list and select the combination with the smallest range.

Solution

1. Step 1: Understand problem constraints

   The problem requires a range covering at least one element from each list, which suggests tracking coverage across lists.

2. Step 2: Evaluate approaches

   Greedy alone fails because it doesn't guarantee minimal range; DP is not suitable due to combinatorial explosion; brute force enumerates all combos but is inefficient. Merging all lists and using two pointers efficiently tracks coverage and minimal range.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer on merged array is known optimal [OK]

Hint: Two pointers on merged array track coverage efficiently [OK]

Common Mistakes:

• Thinking greedy alone suffices
• Assuming DP applies directly
• Using brute force for large inputs

4. Suppose the problem is modified so that each element in nums can be used multiple times for XOR queries (i.e., unlimited reuse), and queries remain the same. Which of the following changes to the optimized approach is correct to handle this variant efficiently?

hard

A. No change needed; the existing trie approach already supports unlimited reuse

B. Use a dynamic programming approach over XOR states instead of a trie

C. Modify the trie to store counts of inserted elements and adjust maxXor to consider reuse

D. Sort queries and nums but do not insert elements multiple times; reuse is implicit

Solution

1. Step 1: Understand reuse impact

   Unlimited reuse means elements can be XORed multiple times, changing the problem semantics.

2. Step 2: Adjust trie to track counts

   Trie nodes must store counts of inserted elements to allow multiple traversals representing reuse.

3. Step 3: Modify maxXor accordingly

   maxXor must consider paths with repeated elements, enabled by counts, to find max XOR with reuse.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Trie with counts supports reuse; naive trie does not [OK]

Hint: Reuse requires tracking counts in trie nodes [OK]

Common Mistakes:

• Assuming no change needed
• Switching to DP unnecessarily
• Ignoring reuse in insertion logic

5. Suppose the problem is modified so that envelopes can be reused multiple times in the nesting sequence. Which of the following algorithmic changes correctly adapts the solution to this variant?

hard

A. Keep the sorting step, but replace LIS with a dynamic programming approach that allows repeated elements by using <= comparisons.

B. Use the same sorting and LIS with binary search approach, but allow bisect_right instead of bisect_left to handle duplicates.

C. Sort envelopes by width ascending and height descending, then use a DP approach similar to unbounded knapsack allowing reuse.

D. Remove sorting and use a greedy approach to pick envelopes repeatedly based on height only.

Solution

1. Step 1: Understand reuse impact

   Allowing reuse breaks LIS assumptions since elements can be repeated multiple times.

2. Step 2: Adapt algorithm

   Sorting still helps, but LIS must be replaced by a DP approach similar to unbounded knapsack that allows multiple uses of the same envelope.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP with reuse and sorting is correct adaptation [OK]

Hint: Reuse means LIS no longer applies; use unbounded knapsack DP [OK]

Common Mistakes:

• Trying to fix LIS with bisect_right
• Using <= in LIS but still only one use per envelope
• Ignoring sorting or using greedy