Trapping Rain Water


@thalaivva Yes sir, that was a mistake in the algorithm. Thanks for rectifying the issue. It has been corrected now. :D

There's an O(n) runtime and O(1) space algorithm too. It works by tracking the space not filled by water, then subtracting that from the "box" formed by the length of the array and the maximum height. Iterate through the height array 3 times:
 Starting from the left, sum up the open space under the maximum height which is entirely to the left of all blocks. This is done by tracking the maximum height you've seen so far, and each time that a new height exceeds that, increase the amount of open space by the product of the difference between the new height and the old, and the horizontal distance between the end of the array and your current location.
 Repeat the previous, except this time start from the right end and track how much open space is entirely to the right in the same way.
 Find the sum of all values in the height array (i.e., how many square units are filled by blocks)
Sum the nonwater area you got from those three iterations, then subtract the sum from the product of the maximum height and the length of the height array. That gives you the amount of water your structure holds.
In Python (1st and 3rd iterations described above are combined in this example):
#Python class Solution(object): def trap(self, heights): """ :type heights: List[int] :rtype: int """ # openSum = amount of confirmed open space we have so far (area under maxHeight) # filledSum = amount of space filled with blocks # maxHeight = height of highest wall found so far openSum=0 maxHeight = 0 filledSum = 0 # Frontwards for i in range(len(heights)): if heights[i] > maxHeight: openSum = openSum + ((heights[i]maxHeight)*(i)) maxHeight = heights[i] filledSum = filledSum + heights[i] # Track how many blocks there are maxHeight = 0 # Backwards for i in range(len(heights)1,1,1): if heights[i] > maxHeight: openSum = openSum + ((heights[i]maxHeight)*(len(heights)(i+1))) maxHeight = heights[i] return (maxHeight*len(heights))(openSum+filledSum) # Size of full box, minus open space, minus space filled with blocks
You could also use 2 pointers like in Solution #4 to combine all 3 iterations into one, but that doesn't change the time complexity.

The DP solution certainly does not need O(n) space.
 We iterate forwards as usual, keeping the index of the last maximal height. Let this index be called peak
 We iterate backwards until peak, keeping track of the last seen maximum, and subtracting excess rainwater
Where excess = peak  currentMaximum
/** * @param {number[]} height * @return {number} */ var trap = function(height) { if (height.length < 1) return 0 peak = 0 currMax = height[0] rain = 0 for (i = 0; i < height.length; i++) { currHeight = height[i] if (currHeight < currMax) { rain += currMax  currHeight } else { currMax = currHeight peak = i } } currMax = height[height.length  1] for (i = height.length  1; i > peak; i) { currHeight = height[i] if (currHeight > currMax) { currMax = currHeight } console.log('subtracting', (height[peak]  currMax), 'at', i) rain = height[peak]  currMax } return rain };```

// 2 pointers, shrinking window. fix Math.max(leftMax, rightMax) side, move the other side
public int trap4(int[] A) { // input validation if (A == null  A.length < 3) { return 0; } // 2 pointers, sliding window int sum = 0, leftMax = 0, rightMax = 0; for (int lo = 0, hi = A.length  1; lo < hi; ) { // update leftMax and rightMax leftMax = Math.max(leftMax, A[lo]); rightMax = Math.max(rightMax, A[hi]); // fix left side, move right side if (leftMax > rightMax) { sum += rightMax  A[hi]; hi; // fix right side, shrink left side } else { sum += leftMax  A[lo]; lo++; } } return sum;

class Solution(object): # This solution has time complexity O(n**2), space complextity O(n), it has Time Limit Exceeded error def trapBruteForce(self, height): """ :type height: List[int] :rtype: int """ result = 0 for i in range(1,len(height)1): l_max = max(height[:i+1]) r_max = max(height[i:]) h = min(l_max, r_max) result += hheight[i] return result # This solution has time complexity O(n), space complexity o(n) def trapDP(self, height): N = len(height) if N < 3: return 0 result = 0 l_max, r_max = [0]*N, [0]*N l_max[0] = height[0] for i in range(1, N): l_max[i] = max(height[i], l_max[i1]) r_max[N1] = height[N1] for i in range(N2, 1, 1): r_max[i] = max(height[i], r_max[i+1]) for i in range(1, N1): result += min(l_max[i], r_max[i])  height[i] return result # This solution has time complexity O(n), space complexity o(n) def trapStack(self, height): result, i = 0, 0 st = [] while i < len(height): while st and height[st[1]] < height[i]: t = st.pop() if not st: break; dist = i  st[1] 1 h = min(height[i], height[st[1]])  height[t] result += h * dist st.append(i) i += 1 return result # This solution has time complexity O(n), space complexity o(1) def trapTwoPointers(self, height): N = len(height) if N < 3: return 0 result, l, r = 0, 1, N2 l_max = height[0] r_max = height[N1] while (l <= r): if l_max <= r_max: l_max = max(l_max, height[l]) result += l_max  height[l] l += 1 else: r_max = max(r_max, height[r]) result += r_max  height[r] r = 1 return result

@kickasowen #11 you're right
@abhinavbansal0 subproblems in approach 2# are disjoint, it's also a dividedandcounter method

Kind of similar to #2, but without extra space usage and less iterations. But still running one unnecessary time on right side of max. So not as good as #4. But it might be more cache and branch prediction friendly friendly? Not sure.
Complexity:
Time = O(N)  worst 2N, best N, average 1.5N
Space = O(1)class Solution { public: int trap(const std::vector<int>& heights) const { int water = 0; int water_at_max = 0; int max_h = 0; auto max_idx = 0u; auto counter = 0u; for (auto h : heights) { if (max_h <= h) { max_h = h; max_idx = counter; water_at_max = water; } water += max_h  h; ++counter; } water = 0; max_h = 0; for (auto itr = heights.rbegin(); itr != heights.rend()  max_idx; ++itr) { if (max_h <= *itr) max_h = *itr; water += max_h  *itr; } return water_at_max + water; } };