42.Trapping-Rain-Water
42. Trapping Rain Water
้ข็ฎๅฐๅ
https://leetcode.com/problems/trapping-rain-water/
้ข็ฎๆ่ฟฐ
ไปฃ็
Approach 1: Brute force
Intuition
Do as directed in question. For each element in the array, we find the maximum level of water it can trap after the rain, which is equal to the minimum of maximum height of bars on both the sides minus its own height.
Algorithm
Initialize ans = 0
Iterate the array from left to right:
Initialize max_left = 0 and max_right = 0
Iterate from the current element to the beginning of array updating:
max_left=max(max_left, height[j])
Iterate from the current element to the end of array updating:
max_right=max(max_right, height[j])
Add min(max_left, max_right) โ height[i] to ans
Complexity Analysis
Time complexity: O_(_n^2). For each element of array, we iterate the left and right parts.
Space complexity: O(1) extra space.
Approach 2: Dynamic Programming
Algorithm
Find maximum height of bar from the left end upto an index i in the array left_max.
Find maximum height of bar from the right end upto an index i in the array right_max.
Iterate over the height array and update ans:
Add min(max_left[i], max_right[i]) โ height[i] to ans
Approach #3 Using stacks
Intuition
Instead of storing the largest bar upto an index as in Approach 2, we can use stack to keep track of the bars that are bounded by longer bars and hence, may store water. Using the stack, we can do the calculations in only one iteration.
We keep a stack and iterate over the array. We add the index of the bar to the stack if bar is smaller than or equal to the bar at top of stack, which means that the current bar is bounded by the previous bar in the stack. If we found a bar longer than that at the top, we are sure that the bar at the top of the stack is bounded by the current bar and a previous bar in the stack, hence, we can pop it and add resulting trapped water to ans.
Approach #4 Using two points
Algorithm
Initialize left pointer to 0 and right pointer to size-1
While left<right, do:
If height[left] is smaller than height[right]
If height[left] โฅ left_max, update left_max
Else add left_max โ height[left] to ans
Add 1 to left.
Else
If height[right] โฅ right_max, update right_max
Else add right_max โ height[right] to ans
Subtract 1 from right.
Complexity analysis
Time complexity: O_(_n). Single iteration of O(n)
Space complexity: O(1) extra space. Only constant space required for left, right, left_max and right_max.
Last updated