1. Container With Most Water

Link to the problem

Description

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

Note: You may not slant the container andnis at least 2.

Examples

Input: [1, 1], Output: 1
The two lines are (0, 0)--(0, 1) and (1, 0)--(1,1), the rectangle they form has height 1, and width 1. So the area is 1.

Input: [2, 1, 3], Output: 4
The best lines are (0, 0)--(0, 2) and (2, 0)--(2, 3), the rectangle they form has height 2, and width 2. So the area is 4.

Idea

We want to find i < j, such that (j - i)min(ai, aj) is maximized.
Assume we are now at i = left and j = right, and by symmetry, ai < aj, then by decrementing j and fix that i, we can only make their minimum smaller, but their difference is strictly smaller, so we can never increase the area between. Hence, it only makes sense to move the lower bar, and never move the higher one. We use two pointers to maintain the i and j we are searching.

Solution

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

Performance

49 / 49 test cases passed.
Runtime: 16 ms