Leetcode 11 Solution

Leetcode Question Link

https://leetcode.com/problems/container-with-most-water

Thinking Process

Whenever we get a new question, it’s important to first try to transform the question into simple ones, or derive critical properties of the question. For this question, the critical property is:

For container [i, j], if height[i] is greater than height[j], the optimal container within it must be the current one, or the one within [i, j - 1].

Proof: For container [i, j], if height[i] is greater than height[j], the current container can contain (j - i) * height[j] water. If the optimal container is not [i, j] and not within [i, j - 1], the region [j - 1, j] has to be included in the optimal container. Assuming the left boundary is i', the optimal container can only hold less than or equal to (j - i') * height[j]. However, this is smaller than the current container, which hold (j - i) * height[j] water.

So the statement of the optimal container is not [i, j] and not within [i, j - 1] is false.

With this property, the problem becomes eays. We can just use two pointers, starting from beginning and the end. Walk the pointer who has a lower height. Memorize the current optimal container while walking.

Time & Space Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Solution

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();

        int l = 0;
        int r = n - 1;
        int maxv = 0;

        while (l < r)
        {
            maxv = std::max(maxv, (r - l) * std::min(height[l], height[r]));

            if (height[l] == height[r])
                l++, r--;
            else if (height[l] > height[r])
                r--;
            else
                l++;
        }

        return maxv;
    }
};

Learning

• Try to derive properties first if you can’t derive a solution to the question.