[LeetCode 11] 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.

Difficulty
medium

Related Problems
[LeetCode 42] Trapping Rain Water H [LeetCode 84] Largest Rectangle in Histogram H

Analysis

We can use greedy algorithm to solve this, which means that we update a max area each time we iterate over the provided sequence. Use to indexsers i, and j pointing to begin and end of containers, record the current area and move forward/backward the indexer when the line is shorter.

Time complexity is O(n) since we only need to loop one time over the sequence.

Solutions

1. Cpp solution 26ms

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

1. Go solution 29ms

func maxArea(height []int) int {
    n := len(height)
    i, j := 0, n-1
    var area int
    for i < j {
        area = max(area, (j-i)*min(height[i], height[j]))
        if height[i] < height[j] {
            i++
        } else {
            j--
        }
    }
    return area
}

func max(a, b int) int {
    return int(math.Max(float64(a), float64(b)))
}

func min(a, b int) int {
    return int(math.Min(float64(a), float64(b)))
}