Leetcode: 11 Container With Most Water (medium)

Lets take a look at the 11th problem (Category: Array)

Statement: 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.

Input: height = [2, 4, 2, 3, 5, 4, 2]
Output: 16

Input: height = [1, 2]
Output: 1

Explanation: We can solve this problem by using brute force algorithm also but here we will be discussing the optimized solution.

Area of rectangle = length * breadth

lets consider first and last pole i.e (1, 7). Here, the length for calculating the area will be 1 and breadth would be distance between 1st and last pole i.e (8–0)8. So area = 1*8 = 8

Now if we calculate the area for next poles i.e (1, 3), (1, 8), (1, 4), notice that the length is going to remain the same i.e the length of the shortest pole and also, the breadth keeps reducing; so the area keeps reducing as well. This would definitely not get us the maximum area.

lets hop to second pole i.e 8 (8, 7), Here, the length (shortest pole) will be 7 and breadth will be 7 (last pole’s distance — second pole’s distance i.e 8–1 = 7. So area = 7*7 = 49

The above example is a but peculiar. The maximum height in the above example which could give us the maximum breadth is the pair (8,7). If we move any further i.e third pole, fourth pole etc, we are just reducing the breadth in an attempt to search for maximum length and that would no longer give us the maximum area.

This gives us the condition that if the length of the right pole is greater than the length of the left pole, then we chose the next pole from left. If the length of the right pole is lesser than the length of left pole, then we choose the next pole from right and check for the area.

Javascript code:

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
   var n = height.length;
   var left = 0;
   var result;
   var right = n - 1
   while(left < right) {
        // Select the minimum of left and right pointer heights for area calculation
        var area = min(height[left], height[right]) * (right - left)
        // Select the maximum of result so far and current area result
        result = max(result, area)
        
        // If the current l height is less than r height,
  // there is no use selecting l for next iteration because, width decreases, so area cant increase
  // So l++(select r, dont select l for next iteration)
      if (height[left] < height[right]) {
        left++
      } else {
        right--
      }
    }
    return result
};
function min(a,b){
    if (a<b){
        return a
    }
    return b
}
function max(a, b){
    if (a>b) {
        return a
    }
    return b
}

Time complexity: O(n)
Space complexity: O(1)