How do you solve Trapping Rain Water on LeetCode?

Trapping Rain Water (LeetCode #42) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The water trapped above a bar depends on the minimum of the maximum heights to its left and right.

What is the brute force solution for Trapping Rain Water?

The brute force approach for Trapping Rain Water is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach calculates the trapped water for each bar by determining the maximum height of the bars to the left and right of it. The water trapped on top of each bar is the minimum of these two heights minus the height of the bar itself. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Trapping Rain Water?

Trapping Rain Water uses the following concepts: Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack. The recommended patterns to study are: Two Pointers, Dynamic Programming.

What are the interview tips for Trapping Rain Water?

Always clarify the problem and constraints before jumping into coding. Discuss your thought process and any edge cases you can think of. Practice explaining your code as you write it, as communication is key in interviews.

What are common mistakes when solving Trapping Rain Water?

Not considering edge cases like flat surfaces or increasing/decreasing sequences. Confusing the left and right maximum calculations, leading to incorrect water calculations.

#42

Trapping Rain Water

Hard

ArrayTwo PointersDynamic ProgrammingStackMonotonic StackTwo PointersDynamic Programming

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal approach uses two pointers to traverse the height array from both ends towards the center. By maintaining the maximum heights seen from both sides, we can efficiently calculate the trapped water without redundant calculations.

⚙️

Algorithm

6 steps

1Step 1: Initialize two pointers, left and right, at the start and end of the height array, and two variables left_max and right_max to track the maximum heights.
2Step 2: While left is less than right, compare left_max and right_max.
3Step 3: If left_max is less than right_max, calculate the trapped water at the left pointer and move the left pointer to the right.
4Step 4: If right_max is less than or equal to left_max, calculate the trapped water at the right pointer and move the right pointer to the left.
5Step 5: Continue until the two pointers meet.
6Step 6: Return the total trapped water.

solution.py14 lines

1def trap(height):
2    left, right = 0, len(height) - 1
3    left_max, right_max = 0, 0
4    water = 0
5    while left < right:
6        if height[left] < height[right]:
7            left_max = max(left_max, height[left])
8            water += left_max - height[left]
9            left += 1
10        else:
11            right_max = max(right_max, height[right])
12            water += right_max - height[right]
13            right -= 1
14    return water

ℹ

Complexity note: The time complexity is O(n) because we traverse the height array once, and the space complexity is O(1) since we only use a few extra variables.

1The water trapped above a bar depends on the minimum of the maximum heights to its left and right.
2Using two pointers reduces the need for nested loops, improving efficiency.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.