[LeetCode Road] Container With Most Water - Solution/C++

11. Container With Most Water

Question:

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

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 represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Input: height = [1,1]
Output: 1

Input: height = [4,3,2,1,4]
Output: 16

Input: height = [1,2,1]
Output: 2

Constraints:

n == height.length

2 <= n <= 10⁵

0 <= height[i] <= 10⁴

Source code

Verion 1

Idea:
Declare two variables, one is the leftmost of vertical lines and the other is the rightmost of vertical lines.
First, we can get the container with largest length of x-axis. Then, compare the leftmost line with the rightmost line for finding the smallest one. It will be moved close to the other. (It means moving to the next line and try to find the larger container)

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

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