LeetCode #11 Container With Most Water Solution & Explanation

LeetCode Problem

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

LeetCode #11 Examples
LeetCode #11 Constraints

Solution

The first though when I saw this question is use iteration from the first index to the last index.

And use a variable to store the max Area

C# Solution

Solution1 ➡ Too slow

public class Solution {
    public int MaxArea(int[] height) {
     
        int l = height.Length;
        int max = 0;
        int maxH = -1;
        
        for(int i = 0; i<l-1;i++)
        {
            if(height[i] < maxH)
            {
                continue;    
            }
            
            for(int j =i+1; j<l;j++)
            {
                int cal = Math.Min(height[i],height[j]) * (j-i);
                //max = cal>max? cal : max;
                if(cal>max)
                {
                    maxH = height[i];
                    max = cal;
                }
            }
        }
        
        return max;
    }
}

With solution1, it was to slow for this question, so let us try to use two pointer to convergence the array.

Solution2

public class Solution {
    public int MaxArea(int[] height) {
     
        int i = 0;
        int j = height.Length-1;
        int maxAmt = 0;
        int iH;
        int jH;
        int cal;
        
        while(j>i)
        {
            iH = height[i];
            jH = height[j];
            
            //Convergence back and forth
            //which is higher,than will convergence from  the other side
            if(iH>jH)
            {
                cal = jH*(j-i);
                j--;
            }
            else
            {
                cal = iH*(j-i); 
                i++;
            }
            
            if(cal>maxAmt)
                 maxAmt = cal;
            
        }
        return maxAmt;
    }
}

Java Solution

Solution1

class Solution {
    public int maxArea(int[] height) {
        int i = 0;
        int j = height.length-1;
        int maxAmt = 0;
        int iH;
        int jH;
        int cal;
        
        while(j>i)
        {
            iH = height[i];
            jH = height[j];
            
            //Convergence back and forth
            //which is higher,than will convergence from  the other side
            if(iH>jH)
            {
                cal = jH*(j-i);
                j--;
            }
            else
            {
                cal = iH*(j-i); 
                i++;
            }
            
            if(cal>maxAmt)
                 maxAmt = cal;
            
        }
        return maxAmt;
    }
}

Runtime : 4ms、3ms、2ms

Python3 Solution

Solution1

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i = 0;
        j = len(height)-1;
        maxAmt = 0;
        
        while(j>i):
            iH = height[i];
            jH = height[j];
            
            if(iH>jH):
                cal = jH*(j-i);
                j-=1;
            else:
                cal = iH*(j-i); 
                i+=1;
            
            if(cal>maxAmt):
                 maxAmt = cal;
 
        return maxAmt;

JavaScript Solution

Solution1

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    var i = 0;
    var j = height.length-1;
    var maxAmt = 0;
    var iH;
    var jH;
    var cal;

    while(j>i)
    {
        iH = height[i];
        jH = height[j];


        if(iH>jH)
        {
            cal = jH*(j-i);
            j--;
        }
        else
        {
            cal = iH*(j-i); 
            i++;
        }

        if(cal>maxAmt)
        {
            maxAmt = cal;  
        }
    }
    return maxAmt;
};

Submission Detail

C#

C# Submission Detail

Java

Java Submission Detail

Python3

Python3 Submission Detail

JavaScript

JavaScript Submission Detail

Conclusion

🧡If my solution helps, that is my honor!

"Human nature is like water. It takes the shape of its container."
                                                                                                          Wallace Stevens

The problem link : Container With Most Water – LeetCode

Technology Article

Latest Post

Leave a Reply

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