Skip to content

← leetcode

Container With Most Water

· Medium

LeetCode problem 11

We keep track of two pointers:

  • l for the left side of the container, starting at index 0
  • r for the right side of the container, starting at index height.size()-1

Then, while the condition l < r is still kept, we can iterate through all the possible containers. We can do this with ans = max(ans, min(height[l], height[r]) * (r-l)); as the container has height min(height[l], height[r]) and width r-l.

Then, we can simply increment/decrement the pointer that points to the smaller value. This is because for the container, the limit factor to the amount of water it can hold is the smaller value between min(height[l], height[r]). Therefore, we change it in the hopes of finding a larger value.

However, if both pointers have the same value, then we can simply increment the left pointer and decrement the right pointer at the same time. This is because, we know regardless of what how tall height[l+1] and height[r-1] are, it is impossible for the new container to hold a larger amount of water. Therefore, we should change both in the hopes that both point to a larger value.

code

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

complexity

  • Time: O(n) where n denotes the number of elements inside of height
  • Space: O(1)

time taken

  • 3 minutes and 41 seconds