# Trapping Rain Water

• The explanation to your last approach is confusing.. Specifically the algorithm when height[left] > height[right] you ask to increment left but in your code.. you are decrementing right in that case..

• @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 non-water 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.

1. We iterate forwards as usual, keeping the index of the last maximal height. Let this index be called peak
2. 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
};`````````

• its so hard

• I did approach 4, but with 2 arrays instead of 2 pointers.

• ``````// 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;``````

• Among these solutions, stack solution is the least obvious to me.

• ``````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 += h-height[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[i-1])

r_max[N-1] = height[N-1]
for i in range(N-2, -1, -1):
r_max[i] = max(height[i], r_max[i+1])

for i in range(1, N-1):
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, N-2
l_max = height[0]
r_max = height[N-1]
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
``````

• #2 is not DP actually, because the problem is not divided into 2 sub-problems, but 2 partial problems. It's just memoization. Although memoization is often used with DP, they're different concepts. Don't be misleading.

• @kickasowen #11 you're right
@abhinavbansal0 subproblems in approach 2# are disjoint, it's also a divided-and-counter method

• There is an easier linear solution with constant memory: Find the global maximum. Find the last index of global maximum. Then do approach 2/4: scan right from start to last max, then scan left from end to last max. What can be easier?

• 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;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.