π‘ Problem Formulation: The ‘trapping rain water’ problem involves calculating the total amount of rainwater that can be trapped within a given set of non-negative integer arrays, which represent elevation maps. Each element in the array corresponds to the elevation at that position. For example, given the input array [0,1,0,2,1,0,1,3,2,1,2,1], the desired output is 6 units of trapped rainwater.
Method 1: Brute Force Approach
The brute force approach to the trapping rain water problem calculates the amount of water that can be trapped at every array index by finding the difference between the minimum of maximum heights of bars on both sides and the current height. It is a straightforward but ineffecient method due to its O(n^2) time complexity.
Here’s an example:
def trap_brute_force(height): trapped_water = 0 for i in range(1, len(height) - 1): left_max = max(height[:i]) right_max = max(height[i+1:]) trapped_water += max(min(left_max, right_max) - height[i], 0) return trapped_water print(trap_brute_force([0,1,0,2,1,0,1,3,2,1,2,1]))
Output:
6
This code snippet iterates through each element of the height array, excluding the first and last elements (as no water can be trapped at the ends). At each index, it calculates the maximum height to the left and right, then finds the minimum of those two values. The amount of trapped water is increased by the difference between that minimum and the current height, if positive.
Method 2: Dynamic Programming
This method uses dynamic programming to store the maximum heights to the left and right of every bar in arrays and then uses these to calculate trapped water in a single pass. It vastly improves over the brute force approach with a time complexity of O(n).
Here’s an example:
def trap_dynamic(height): if not height: return 0 left_max, right_max = [0] * len(height), [0] * len(height) left_max[0], right_max[-1] = height[0], height[-1] for i in range(1, len(height)): left_max[i] = max(height[i], left_max[i - 1]) for i in range(len(height) - 2, -1, -1): right_max[i] = max(height[i], right_max[i + 1]) trapped_water = 0 for i in range(len(height)): trapped_water += min(left_max[i], right_max[i]) - height[i] return trapped_water print(trap_dynamic([0,1,0,2,1,0,1,3,2,1,2,1]))
Output:
6
This snippet first initializes two lists to record the maximum height to the left and right of each index. It then populates these lists in two separate loops. Finally, it uses a third loop to calculate the water trapped at each index by taking the minimum of the left and right maxima and subtracting the current height.
Method 3: Two Pointers Approach
The two pointers approach reduces the need for extra space and completes the calculation in one pass with two moving pointers, one from the beginning and one from the end. The time complexity remains O(n), with a lower constant factor compared to the dynamic programming method.
Here’s an example:
def trap_two_pointers(height): if not height: return 0 left, right = 0, len(height) - 1 left_max, right_max = 0, 0 trapped_water = 0 while left < right: if height[left] < height[right]: left_max = max(left_max, height[left]) trapped_water += left_max - height[left] left += 1 else: right_max = max(right_max, height[right]) trapped_water += right_max - height[right] right -= 1 return trapped_water print(trap_two_pointers([0,1,0,2,1,0,1,3,2,1,2,1]))
Output:
6
Instead of storing maxima of the bars to the left and right for all indices, this method computes the trapping water on the go. It maintains two pointers and moves the one with the lower height towards the other pointer, updating the respective max and water trapped at each step.
Method 4: Using a Stack
Method 4 utilizes a stack to keep track of the bars that are bound by walls of water. It processes each bar in one pass (O(n)), using the stack to store and retrieve the indices of previous bars in relation to the current one, thereby computing trapped water between them.
Here’s an example:
def trap_stack(height): trapped_water, current = 0, 0 stack = [] while current height[stack[-1]]: top = stack.pop() if not stack: break distance = current - stack[-1] - 1 bound_height = min(height[current], height[stack[-1]]) - height[top] trapped_water += distance * bound_height stack.append(current) current += 1 return trapped_water print(trap_stack([0,1,0,2,1,0,1,3,2,1,2,1]))
Output:
6
This code uses a stack to process bars in a non-increasing order. Each iteration examines whether the current bar forms a container with the preceding bars in the stack. If so, it calculates the water trapped based on the distance and the height difference, then adds this to the total.
Bonus One-Liner Method 5: Functional Approach
A functional one-liner leverages Python’s built-in functions to implement a concise solution, while sacrificing readability. This is not for production code but may be useful for code golf or understanding the expressive power of Python.
Here’s an example:
trap_oneliner = lambda h: sum(max(min(max(h[:i+1]), max(h[i:])) - h[i], 0) for i in range(len(h))) print(trap_oneliner([0,1,0,2,1,0,1,3,2,1,2,1]))
Output:
6
This one-liner defines a lambda function that iterates over the indices and calculates the trapped water similarly to the brute force method, utilizing the max
and min
functions for every position. It is compact but runs with O(n^2) complexity due to nested max operations.
Summary/Discussion
- Method 1: Brute Force Approach. Straightforward logic. Excessive time complexity. Unsuitable for large datasets.
- Method 2: Dynamic Programming. Optimal time complexity. Uses extra space. Efficient for a single calculation with non-repeated building heights.
- Method 3: Two Pointers Approach. Optimal time complexity. Space-efficient. Requires understanding of the water-level and elevation dynamic.
- Method 4: Using a Stack. Good time complexity. Can be intuitive for those familiar with stacks. More complex logic compared to other methods.
- Method 5: Functional Approach. Elegant one-liner. Poor performance due to high time complexity. Useful for learning Python’s functional abilities.