Link to Question

MEDIUM

Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example

Input:

height = [1,8,6,2,5,4,8,3,7]

Output:

49

Explanation:
The above vertical lines are drawn at the points (0,1), (1,8), (2,6), (3,2), (4,5), (5,4), (6,8), (7,3), and (8,7). The two lines that form the container are at (1,8) and (8,7), and the container holds 49 units of water.

---

Constraints

• n == height.length
• 2 ≤ n ≤ 10⁵
• 0 ≤ height[i] ≤ 10⁴

---

Solution: Two Pointers

• Time Complexity: O(n), where n is the number of elements in the array.
• Space Complexity: O(1), as only a constant amount of extra space is used.

C++

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