In this problem we are tasked with finding the maximum size of a container to store water in. How this works is, we are given an integer array called height in it there are heights given for n vertical lines (n being the size of the array).
The vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
We are to find the two points/lines that we can use to represent the maximum amount of space that can be used in the middle to store water.
We can note down that the X axis = indexes in the height array, and the Y axis = heights[i]. Each element in the array represents the height of a vertical line we can plot on the graph.
Finally, once we have found the two points, we are to return the maximum amount of water that can be stored in the graph between the two maximum points that provide this. Refer to this example for context on what this would look like:
Solution Explanation
Before we actually implement the solution we need to mark down the variables we will need to consider:
Size of the array = n
Y-axis = heights[i]
X-axis = i
area = (rp - lp) * min(height[rp], height[lp]), if the value is negative we leave it as zero
Additionally, heights[i] must have a smaller value than whatever the height at the other point is in order to prevent a spill over given that we need to find the min of the two and use that as the multiplication point.
So, in solution 1, we can utilize a brute force approach where we list out all the possible combinations and mark down what the max amount of water that can be stored is. This is sub-optimal given that the time complexity of this would be O() given that we have to go through each combination.
Now, in terms of solution 2, we need to assess a more algorithmic two pointer approach which utilizes something we call a sliding window and ensures a linear time solution (O(n)). Refer to the following steps:
First initialize a right pointer and left pointer at each end of the array
Calculate the maxArea at this point and mark it down
Shift the minimum pointer of the two forward or backward:
If it is the left pointer we shift it forward
If it is the right pointer we shift it backward
If both pointers have equal heights, we can freely choose whichever pointer to shift forward or backward
Calculate the maxArea and if it surpasses the existing maxArea we replace it.
Repeat steps 1~4 until the index of the left and right pointer both meet at the same point.
Implementation
Implementation for the brute force approach (sub optimal, but it works):
class Solution:
def max(self, height: List[int]) -> int:
res = 0
for lp in range(len(height)):
for rp in range(lp+1, len(height)):
# Calculation used here is to find area of rectangle
area = (rp-lp)*min(height[rp], height[lp])
res = max(area, res)
return res
Here's the implementation for the sliding window approach that has an optimal time complexity of O(n):
class Solution:
def maxArea(self, height: List[int]) -> int:
res = 0
# We set the lp to start of array and rp to end of array
lp, rp = 0, len(height) - 1
# Check to ensure lp is less than rp for a valid container
while lp < rp:
area = (rp - lp) * min(height[rp], height[lp])
# Update res if area bigger or just leave it at current res
res = max(res, area)
if height[lp] < height[rp]:
# Update lp if it is less than rp
lp+=1
else:
# Update rp if it is less than lp
# or
# Update rp if lp=rp
rp -= 1
return res
So, to conclude on what the most optimal solution is. We initialize a left and right pointer on the array to create a sliding window in which the area in between represents the container size to store water in.
We check to see what the min pointer value is and shift the position based on that metric given that each pointer must either be less than the other given that a spill over would happen if not.
An edge case we handle here as well is that if the values of each pointer equal one another we stick to shifting the right pointer backwards given that we could do whichever side we choose as it does not matter.
Finally, in calculating the area of the rectangle we find the difference between the left and right pointers and the multiply it by the minimum height of either pointer.
