OK, I couldn’t figure this one out on my own. After struggling on and off, I eventually gave in and looked at other people’s approaches.

Let me share my thought process.

The first idea was brute force: pick every pair of lines, calculate the volume, and find the maximum.

The logic is correct, but it timed out. I checked the test cases – the data set is quite large.

So what next? We clearly need an approach with complexity lower than $O(n^2)$ to pass.

I thought for a long time. Sorting? Filling water from bottom up? Two pointers, one on each side, moving inward? Or fix the left side and assume the other line is always to the right?

It was all over the place.

Finally I looked at someone else’s solution, and it’s really so easy – I can’t believe I didn’t think of it. Sigh.

The approach is simple: greedy.

Two pointers, one on each end. Record the volume. Move the pointer at the shorter line inward. People online call this the “two-pointer” technique.

During implementation, when the two lines are equal in height, you could move either the left or the right pointer. So the best approach is to use recursion to handle both cases.

Here’s the code. Solving problems can be quite painful, especially for someone slow like me. Keep going!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
public:
    int sum;
    int maxArea(vector<int> &height) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        sum = 0;
        int left = 0;
        int right = height.size() - 1;
        func(left, right, height);
        return sum;
    }
    void func(int left, int right, vector<int> &height)
    {
        if (left < right)
        {
            int min = height[left];
            if (min > height[right])
                min = height[right];
            int tmp = min * (right-left);
            if (tmp > sum)
                sum = tmp;
            if (height[left] > height[right])
            {
                func(left, right-1, height);
            }
            else if (height[left] < height[right])
            {
                func(left+1, right, height);
            }
            else
            {
                func(left+1, right, height);
                func(left, right-1, height);
            }
        }
    }
};