LeetCode Container With Most Water: Linear Time Solution and Sorting

Overview

LeetCode Container With Most Water: 1) Linear Time Solution by two pointers; 2) Sorting first and keeping finding the min/max index in constant time.

LeetCode Container With Most Water

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.

Solution and Precautions: Linear Time Solution and Sorting

(1) Brute force approach: compare every pair of lines to calculate the area between these two lines, keep the max among the O(N^2) pairs, the time complexity is obviously O(N^2) and you might get a TLE error when testing on the big dataset.

(2) Sorting: make a pair for each line as <height, index>, so there would be N such pairs as <a1, 1> <a2, 2>, …, <aN, N>. Sort these N pairs by increasing order on the height value (so ai is in increasing order). Now you can think about how this sort could help before heading into the following context (hint: remember the “Best Time to Buy and Sell Stock” problem, essentially, the solution becomes the same here). Ok, here is the answer, let F(i) denote the max water among the pairs from i-th pair to the last pair after sorting. Now we consider F(i-1), when adding the (i-1)th pair, we need to update the max water, how? since the height is in increasing order, then the (i-1)th pair here must have the shortest line, and the possible amount of water much be this (shortest) height times the difference of indexes between the index value of this (i-1)th pair and the index value among the pairs after. These computation could be done in constant time by keep recording of the minimum index and the maximum index among the pairs after (i-1)th pair. If you check the best time to buy and sell stock problem out, the approach after sorting here is essentially the same one. The total time complexity is O(NlogN + N) = O(NlogN). The following Java code implements this idea and can pass the LeetCode Container With Most Water problem:

class Line {
    public int h;
    public int i;

    Line (int h, int i) {
        this.h = h;
        this.i = i;
    }

    Line () {
        this(0, -1);
    }
}

class LineHeightComparator implements Comparator<Line> {
    public int compare (Line o1, Line o2) {
        return o1.h - o2.h;
    }
}

public class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        if (n < 2)
            return 0;
        Line [] lines = new Line[n];
        for (int i = 0; i < n; ++i) {
            lines[i] = new Line(height[i], i);
        }
        Arrays.sort(lines, new LineHeightComparator());

        int maxResult = 0;
        int minIndex = lines[n-1].i;
        int maxIndex = lines[n-1].i;

        for (int i = n - 2; i >= 0; --i) {
            maxResult = Math.max(maxResult,
                        lines[i].h * Math.max(Math.abs(lines[i].i - maxIndex),
                                              Math.abs(lines[i].i - minIndex)));

            maxIndex = Math.max(maxIndex, lines[i].i);
            minIndex = Math.min(minIndex, lines[i].i);
        }
        return maxResult;
    }
}

(3) Linear approach: If there is no linear approach, then I really think the sorting method is good enough to show your coding ability and knowledge on algorithm. However, there is a even smarter approach though it is not easy to come up with. Basically, we use two pointers say i and j to point to the head and the tail of the original height array. We first calculate the area between line i and line j and try to update the max area if possible. Then we check the lin[i] and lin[j], and advance the pointer to the shorter line by one step (++i or –j). After a linear scan like this, we make sure the max area is found correctly. The idea behind is that, if we encounter a shorter line, say line[i] is shorter than line[j], then there is no need to check other pairs with line[i], if we move j (–j), then the area must only be smaller (why? think about it). The same reasoning applies here for the case where line[j] is shorter. Obviously, this approach takes linear time which is O(N). The following Java code implements this idea and can pass the LeetCode Container With Most Water problem:

public class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1;
        int maxResult = 0;
        while (i < j) {
            maxResult = Math.max(maxResult,
                                 Math.min(height[i], height[j]) * (j - i));
            int t =height[i] < height[j] ? ++i : --j;
        }
        return maxResult;
    }
}

And this problem is really an excellent example to show the process to tackle a difficult problem step by step. One should really try the three approaches out.

Summary

LeetCode Container With Most Water: 1) Linear Time Solution by two pointers; 2) Sorting first and keeping finding the min/max index in constant time.

Written on May 5, 2013