Challenge Description

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 line i is 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 and n is at least 2.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

Native solution

According the challenge description, a naive solution is not hard to figure out.

Time complexity: $O(N^2)$, as we enumerate all the pairs of index in array.

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans = 0;
        int cur = 0;
        for(int i=1; i < height.size(); i++) {
            int h = height[i];
            for(int j=0; j < i; j++) {
                cur = min(h, height[j]) * abs(i - j);
                ans = max(cur, ans);
            }
        }
        return ans;
    }
};

Approach with two pointers

This approach is clever and elegant! It’s time complexity: $O(N)$.

But how to prove it’s right?

I get a non-formal proof from intuition.

• We start with (0, size-1), the result pair maybe in the inner loop, so we narrow one index try to enumerate the pairs.

• If we must to narrow one index, which one to choose? If we narrow the index with higher height, the decreased water must larger, so the only choice is to narrow the index with smaller height.

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

Preparing for an interview? Check out this!