Problem: Container With Most Water

Container With Most Water

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

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

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

Summary

We have to maximize the Area that can be formed between the vertical lines using the shorter line as length and the distance between the lines as the width of the rectangle forming the area.

Solution


Approach 1: Brute Force

Algorithm

In this case, we will simply consider the area for every possible pair of the lines and find out the maximum area out of those.

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

Complexity Analysis

  • Time complexity : O(n^2)O(n2). Calculating area for all \dfrac{n(n-1)}{2}2n(n−1)​ height pairs.
  • Space complexity : O(1)O(1). Constant extra space is used.


Approach 2: Two Pointer Approach

Algorithm

The intuition behind this approach is that the area formed between the lines will always be limited by the height of the shorter line. Further, the farther the lines, the more will be the area obtained.

We take two pointers, one at the beginning and one at the end of the array constituting the length of the lines. Futher, we maintain a variable \text{maxarea}maxarea to store the maximum area obtained till now. At every step, we find out the area formed between them, update \text{maxarea}maxarea and move the pointer pointing to the shorter line towards the other end by one step.

The algorithm can be better understood by looking at the example below:

1 8 6 2 5 4 8 3 7

How this approach works?

Initially we consider the area constituting the exterior most lines. Now, to maximize the area, we need to consider the area between the lines of larger lengths. If we try to move the pointer at the longer line inwards, we won’t gain any increase in area, since it is limited by the shorter line. But moving the shorter line’s pointer could turn out to be beneficial, as per the same argument, despite the reduction in the width. This is done since a relatively longer line obtained by moving the shorter line’s pointer might overcome the reduction in area caused by the width reduction.

Java

public class Solution {
    public int maxArea(int[] height) {
        int maxarea = 0, l = 0, r = height.length - 1;
        while (l < r) {
            maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));
            if (height[l] < height[r])
                l++;
            else
                r--;
        }
        return maxarea;
    }
}

Complexity Analysis

  • Time complexity : O(n)O(n). Single pass.
  • Space complexity : O(1)O(1). Constant space is used.

Golang

func min(a, b int) int {
    if a <= b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a >= b {
        return a
    }
    return b
}


func maxArea(height []int) int {
    maxarea := 0
    l := 0
    r := len(height) - 1
    
    for l < r {
        minHeight := min(height[r], height[l])
        maxarea = max(maxarea, minHeight*(r-l))
        
        if height[r] > height[l] {
            l++
        } else {
            r--
        } 
    }
    
    return maxarea
}

Python

class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxArea = 0
        l = 0
        r = len(height) - 1
        
        while l < r:
            maxArea = max(maxArea, min(height[r], height[l])*(r-l))
            
            if height[l] < height[r]:
                l+= 1
            else:
                r-= 1
        return maxArea
        

If you have any questions, you can comment. Hope, you enjoyed the post. Stay tuned for more interesting posts.

Leave a Reply

Your email address will not be published. Required fields are marked *