11 — Container With Most Water
Restating Info We’re Already Given:
- The height array has n values, each of which is a vertical line.
- The water contained within 2 indices is the minimum of their heights * distance between them
- We’re trying to find the maximum amount of water that can be stored in this heights array.
Questions/Clarifications to Possibly Ask Interviewer (If starting information we’re given isn’t sufficient to begin):
- None, contains enough information
Discuss Naive Solution:
Naively, we could use a double for loop to check each potential pair of indices. That way, we cover each possible combination of left and right walls for containing water, updating the variable representing the maximum water amount.
Discuss Optimal Solution:
More optimally, we could solve this in linear time. To do so, we would have 2 pointers to represent left and right walls. We calculate the amount of water that can be stored between those 2 walls and move one of them to search for a potentially higher amount of water. The one that we move is the shorter of the 2 walls because it’s the one limiting the amount of water that can be stored. We move the limiting wall forward (if left wall) or backward (if right wall) and recalculate the maximum amount of water that can be stored until the left and right indices are equal.
Code Optimal Solution:
Runtime/Space Complexity:
This algorithm runs in linear time with constant space. It terminates when the 2 variables representing indices are equal to one another, which happens in linear time since every iteration moves the pointers closer to one another. Constant space is used as we need 3 integer variables to represent the left wall index, right wall index, and maximum water we can store.
Test Cases:
- only 2 walls (len(height) == 2)
- heights array is strictly increasing (only left wall moves)
- heights array is strictly decreasing (only right wall moves)
- heights array requires moving both walls
