Trapping Rain Water

Problem Description

• As a high level overview on what the problem is here, we are given an array that represents an elevation map. We are tasked with finding all the grids that can be filled out with water in this elevation map, and then returning the total amount of water that can be stored in the end.
• So conditions to consider is that:
  • In order for water to be stored in a position, it must have two cells besides it to store the water in the middle.
  • Water cannot be stored in each edge rather it can only be stored in the middle, given that the water stored cannot spill over.

Solution Explanation

• This problem is technically identical to the container with most water problem, hence making this a sliding window problem of sorts as well.
• In terms of implementing the solution there are some parameters as well as functions we are going to want to keep in mind when implementing a solution for this:
  • To get the amount of water stored at a certain index we need to regard the following equation: min(height[lp],height[rp]) - height[i] = water_in_index. This will tell us if there is water in a position or not, for e.g. if it is 1 it means that specific position has water in it.
  • Given this is an elevation map we are representing through an array called height, the indexes represent the X-axis whereas each value inside represents the Y-axis.
• Now there are two solutions we can appeal to in implementing a solution for this. Number 1 is a brute force approach:
  1. We loop through each index and find the max heights to the left of it and the max heights to the right of it, then fill them out in the equation.
  2. Once we find the min of the max heights we just found from each adjacent height, we proceed to subtract the current positions height from it to see if we can or can't store water in it.
  3. We then repeat this process for each index in the array. This conclusively produces a time and space complexity of O(n) given we create a new sliced array for each pointers side to find what the maximum value is from each side.
  • Refer to the implementation below to see how this can be implemented, additionally here is a visual example of how this approach would work:

• The reason we look for the minimum of the max height from the left and right is because that is the wall that will prevent water from overflowing, if we refer to the one that is larger water will spill over from the other end.
• Now in terms of solution 2, we want to assume a less brute force approach and a sliding window approach of sorts, aside from that we want to assume a constant space complexity without creating multiple sub-arrays:
  1. Initialize two pointers in your array, one to the left at index 0 and one to the right at index len(height) - 1. Thereafter, we want to set the variables maxL and maxR to the maximum heights of the left and right pointers.
  2. Once you have initialized them, proceed to check and see which pointer has the minimum value:
     1. If it is the left pointer, proceed to shift it forward and then carry out the calculation at that point to determine if you can trap water their or not.
     2. If it is the right pointer, proceed to shift it backwards and then carry out the calculation at that point to determine if you can trap water their or not.
     3. If both the maxR and maxL have the same values, proceed to shift the left value forward as we can choose either side but for now we are choosing the left.
  3. Once you consistently do this, you will continue to increment the result till we reach the end where we finally have the total water we can store in the elevation map.
  • Remember the golden function: min(maxL, maxR) - height[i], it will find the difference for you and if it returns a positive integer, that is how much water will be stored at that position.
  • Refer to the following diagram for a visual example:

Implementation

• Brute force implementation:

def trap(height: List[int]) -> int: # TC = O(n), SC = O(n)
	lp, rp, res = 0,0,0
	for i in range(len(height)):
		lp = max(height[0:i+1]) # slice from start to current pos + 1
		rp = max(height[i:len(height)]) # slice from current pos to end
		res += min(lp, rp) - height[i] # increment based on formula
	return res

• Sliding window implementation:

class Solution:
	def trap(self, height: List[int]) -> int:
		if not height: return 0
		
		l, r = 0, len(height) - 1
		maxL, maxR = height[l], height[r]
		res = 0
		
		while l < r:
		# Keep this in mind, the right pointer only ever shifts if it
		# is less than maxL 
			if leftMax < rightMax:
				l += 1
				maxL = max(maxL, height[l])
				res += maxL - height[l]
			else:
				r -= 1
				maxR = max(maxR, height[r])
				res += maxR - height[r]
				
		return res