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. You are given an integer array and a target value. The task is to find all unique quadruplets in the array that sum up to the target. Which approach guarantees an optimal solution that balances time complexity and handles duplicates efficiently?

easy

A. Use four nested loops to check every quadruplet combination.

B. Use dynamic programming to build up solutions for smaller sums and combine them for quadruplets.

C. Apply a greedy algorithm that picks the largest elements first to reach the target sum quickly.

D. Sort the array, then use a hash map to store all pairs of sums and find complementary pairs without index overlap.

Solution

1. Step 1: Understand problem constraints

   Finding quadruplets summing to target requires checking combinations efficiently and avoiding duplicates.

2. Step 2: Evaluate approaches

   Brute force (four loops) is correct but inefficient. Greedy fails because sum combinations are not monotonic. DP is not suitable here. Hash map storing pairs of sums allows O(n^2) preprocessing and efficient lookup, handling duplicates by sorting and index checks.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Hash map approach balances efficiency and correctness [OK]

Hint: Hash map of pairs enables efficient quadruplet search [OK]

Common Mistakes:

• Thinking greedy or DP solves 4Sum efficiently

2. You are given an unsorted array and a number k. The task is to find a subset of k elements such that the difference between the maximum and minimum elements in this subset is minimized. Which algorithmic approach guarantees an optimal solution efficiently?

easy

A. Use a greedy approach by always picking the smallest element and then the next closest elements without sorting.

B. Sort the array and use a sliding window of size k to find the minimum difference between the first and last elements in each window.

C. Use dynamic programming to store minimum differences for all subsets of size k.

D. Use brute force to generate all subsets of size k and compute their differences.

Solution

1. Step 1: Understand the problem constraints

   Finding a subset of k elements with minimum max-min difference requires contiguous elements after sorting.

2. Step 2: Identify the optimal approach

   Sorting the array places elements in ascending order, so the minimum difference subset must be a contiguous window of size k. Sliding window efficiently checks all such windows.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + sliding window is classic for minimum range in subsets [OK]

Hint: Sort then slide window to find minimal range [OK]

Common Mistakes:

• Trying greedy without sorting misses optimal subsets
• Using DP unnecessarily complicates the problem
• Brute force is correct but impractical

3. What is the time complexity of the optimal in-place merge algorithm that uses two pointers starting from the end of the arrays to merge two sorted arrays of sizes m and n?

medium

A. O((m + n) log(m + n)) due to sorting after merging

B. O(m * n) because of nested loops comparing elements

C. O(m + n) because each element is processed exactly once

D. O(m + n) but with O(m + n) extra space for temporary storage

Solution

1. Step 1: Identify the loops

   The algorithm uses a single while loop that processes each element from the end once.

2. Step 2: Analyze operations per element

   Each element from nums1 and nums2 is moved at most once, so total operations are proportional to m + n.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear time complexity with constant extra space [OK]

Hint: Two-pointer merge is linear time, no sorting needed [OK]

Common Mistakes:

• Confusing with sorting complexity
• Assuming nested loops cause quadratic time

4. The following code attempts to implement the Dutch National Flag algorithm but contains a subtle bug. Identify the line causing the bug.

medium

A. Line where mid is incremented after swapping 0

B. Line where low is incremented

C. Line where mid is incremented after encountering 1

D. Line where high is decremented after swapping 2

Solution

1. Step 1: Identify pointer updates after swapping 0

   After swapping nums[low] and nums[mid] when nums[mid]==0, both low and mid must be incremented to avoid infinite loops or incorrect ordering.

2. Step 2: Locate missing increment

   The code increments low but does not increment mid after swapping 0, causing mid to stay at the same index and potentially reprocessing the same element indefinitely.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing mid increment after swapping 0 causes infinite loop or wrong output [OK]

Hint: mid must increment after swapping 0 to progress [OK]

Common Mistakes:

• Forgetting mid increment after swap
• Confusing pointer roles
• Incrementing mid after swapping 2

5. Suppose the problem is extended so that the backspace character '#' can be repeated multiple times consecutively, and you want to optimize the algorithm to handle very long sequences of '#' efficiently. Which modification to the two-pointer forward approach is most appropriate?

hard

A. Process the strings from the end with two pointers, skipping characters affected by consecutive backspaces on the fly.

B. Modify the algorithm to skip over consecutive '#' characters by counting them and adjusting the write pointer accordingly in one step.

C. Use a stack to push characters and pop for each '#' to handle multiple backspaces efficiently.

D. Preprocess the strings by removing all '#' characters before comparison.

Solution

1. Step 1: Understand the challenge with consecutive backspaces

   Multiple consecutive '#' characters can cause multiple deletions, which can be inefficient if processed one by one in a forward pass.

2. Step 2: Identify the best approach

   Processing from the end with two pointers allows skipping over characters affected by multiple backspaces efficiently without reconstructing strings or counting '#' explicitly.

3. Step 3: Why other options fail

   Counting '#' forward is complex and error-prone; stacks use extra space; preprocessing removes needed info and breaks order.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backward two-pointer approach handles consecutive backspaces efficiently [OK]

Hint: Backward two-pointer skips multiple backspaces efficiently [OK]

Common Mistakes:

• Trying to count '#' forward complicates logic
• Using stacks increases space unnecessarily
• Preprocessing removes order and breaks correctness