Let's Code_: Leetcode Medium: Container with most water

Tuesday, July 19, 2022

Leetcode Medium: Container with most water

Problem Name: Container with most water

Problem Description: https://leetcode.com/problems/container-with-most-water

Problem Approach used: This problem can be solved with multiple approaches. The naive solution calculates the water content in all possible containers, compares and returns the maximum water that can be contained. It is O(n^2) time solution with O(1) auxiliary space.

Other "smarter" solution takes O(n) time with O(1) space. It makes use of the 2-pointer technique.

Time Complexity: O(n) worst-case time complexity and O(1) auxiliary space complexity.

Solution 1:

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

Solution 2:

class Solution {
    public int maxArea(int[] height) {
        // 2 pointer technique
        int smallerIndex=0, greaterIndex=height.length-1;
        int maxAreaSoFar = 0;
        while (smallerIndex < greaterIndex) {
            if (height[smallerIndex] >= height[greaterIndex]) {
                maxAreaSoFar = Math.max(maxAreaSoFar, 
                                        height[greaterIndex] * (greaterIndex - smallerIndex));
                greaterIndex-- ;
            } else if (height[smallerIndex] < height[greaterIndex]) {
                maxAreaSoFar = Math.max(maxAreaSoFar,
                                        height[smallerIndex] * (greaterIndex - smallerIndex));
                smallerIndex++;
            } else {
                ;
            }
        }
        return maxAreaSoFar;
    }
}