~/leetcode $ 11. Container-With-Most-Water

The maximum amount of water that a given ‘container’ can store is the min height of the two ‘walls’ times the width. This feels like a two pointer question (one pointer for the left wall and another one for the right), the question is where do we initialise the two pointers and how do the pointers move.

We could initialise both of the pointers from the start but it is not obvious how we would update our left and right walls iteratively. Another idea would be to initialise the left pointer at the start of the list and initialise the right pointer at the end of the list. Then, for that width (width of the whole list) that is the largest possible container. Then, we take the smaller wall out of the two and move that pointer inwards. The new container is guaranteed to be the largest container for that width (as we eliminate the smaller wall and the area is dependent on the min value of the two walls). We keep track of the max area that we have come across while iterating and return this once the left and right pointers intersect.

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0;
        int r = height.size() - 1;
        int maxArea = 0;
        while (l < r) {
            int area = min(height[l], height[r]) * (r - l);
            maxArea = max(area, maxArea);
            if (height[l] < height[r]) {
                ++l;
            } else {
                --r;
            }
        }

        return maxArea;
    }
}

Time Complexity: O(n)

Space Complexity: O(1)

Time Taken: 6m 51s