LeetCode: Container With Most Water

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) 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.

---

A straight way is to compute every possible combinations, which will take O(n^2) time. We can reduce it to O(n) for this problem. Starting from the left most line and right most line, maximum volume can be computed and updated. Then we move "forward" the shorter line.

Proof: Assume the current volume is left_line * (right_idx - left_idx) with that right_line is higher, and we move it. Then the volume next time is min(left_line, right_line') * (right_idx - left_idx - 1). If right_line' is shorter than left_line, apparently this volume will be less than the previous one since right_line' < left_line and (right_idx - left_idx - 1) < (right_idx - left_idx). If right_line' is taller than left_line, then the volume will be left_line * (right_idx - left_idx - 1), which is also smaller than the previous one. Hence, we don't need to move the higher line forward.

C++ Code:

/*
 * func: container_most_water
 * goal: find the container that can hold the most amount of water
 * @param height: the vector of line heights
 * return: return the largest volume
 */
/*
 *Start from the first one and the largest one, and keep updating the
 *area at the same time. Each time move forward the shorter one 'forward'
 *Complexity: time O(n), space O(1)
 */
int container_most_water(const vector<int> &height){
    //Corner case
    if(height.size() <= 1){
        throw std::invalid_argument("The input argument is invalid, container cannot be formed");
        return 0;
    }
    
    //left index and right index
    int left_idx = 0;
    int right_idx = height.size()-1;
    
    int ret = 0;
    while(left_idx < right_idx){
        //Compute current area
        int curr_area = min(height[left_idx], height[right_idx]) * (right_idx-left_idx);
        //Update maximum area
        ret = max(ret, curr_area);
        //Move forward
        height[left_idx] >= height[right_idx] ? --right_idx : ++left_idx;
    }
    
    return ret;
}

Python Code:

# func: choose two lines from the vector to form the biggest container
# @param height: the list of heights
# @return: the biggest volume
# complexity: time O(n), space O(1)
def max_area(height):
    #If there is only one line, container cannot be formed
    if len(height) <= 1:
        raise Exception("INVALID ARGUMENT")
        return 0
    else:
        #start index
        left_idx = 0
        right_idx = len(height) - 1
        max_volume = 0
        while left_idx < right_idx:
            #Compute current volume
            curr_volume = min(height[left_idx], height[right_idx]) * (right_idx - left_idx)
            #Update max_volume
            max_volume = max(curr_volume, max_volume)
            #Move index
            if height[left_idx] <= height[right_idx]:
                left_idx += 1
            else:
                right_idx -= 1

        return max_volume