# Leetcode 11 Solution

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.