Solution For Container With Most Water

Container With Most Water is a classic two-pointer approach problem on LeetCode. The problem statement reads:
Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

The idea behind solving this problem is to use the two-pointer approach, where we use two pointers, left and right, to traverse the array from both ends. We will start with the widest container in the array, which is represented by the left and right pointers, and we will keep moving the pointers towards each other until they meet.

During the traversal, we calculate the area of the container bounded by the two pointers, which is given by the formula (min(a[left], a[right]) * (right – left)). We keep track of the maximum area encountered so far and return it as the final answer.

Here’s the detailed solution to the Container With Most Water problem:

Algorithm:
1. Initialize two pointers, left = 0 and right = n-1, where n is the length of the input array.
2. Initialize a variable maxArea to 0, which will store the maximum area encountered so far.
3. While left < right:
a. Calculate the area of the container bounded by the two pointers, which is given by the formula (min(a[left], a[right]) * (right – left)).
b. If the calculated area is greater than maxArea, update maxArea to the calculated area.
c. If a[left] < a[right], increment left by 1.
d. Else, decrement right by 1.
4. Return maxArea as the final answer.

Let’s understand the above algorithm through an example:

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

Step 1: Initialize two pointers, left = 0 and right = n-1, where n is the length of the input array.

Left pointer –> | 1,8,6,2,5,4,8,3,7 |
Right pointer –> | 1,8,6,2,5,4,8,3,7 |

Step 2: Initialize a variable maxArea to 0, which will store the maximum area encountered so far.

maxArea = 0

Step 3: While left < right:
a. Calculate the area of the container bounded by the two pointers, which is given by the formula (min(a[left], a[right]) * (right – left)).

At the beginning, left = 0, right = 8, and a[left] = 1, a[right] = 7
Area = min(a[left], a[right]) * (right - left) = min(1, 7) * (8 - 0) = 8
maxArea = max(maxArea, Area) = max(0, 8) = 8

While moving the pointers:

At left = 1, right = 8, and a[left] = 8, a[right] = 7
Area = min(a[left], a[right]) * (right - left) = min(8, 7) * (8 - 1) = 56
maxArea = max(maxArea, Area) = max(8, 56) = 56

At left = 1, right = 7, and a[left] = 8, a[right] = 3
Area = min(a[left], a[right]) * (right - left) = min(8, 3) * (7 - 1) = 24
maxArea = max(maxArea, Area) = max(56, 24) = 56

At left = 1, right = 6, and a[left] = 8, a[right] = 8
Area = min(a[left], a[right]) * (right - left) = min(8, 8) * (6 - 1) = 40
maxArea = max(maxArea, Area) = max(56, 40) = 56

At left = 1, right = 5, and a[left] = 8, a[right] = 4
Area = min(a[left], a[right]) * (right - left) = min(8, 4) * (5 - 1) = 32
maxArea = max(maxArea, Area) = max(56, 32) = 56

At left = 1, right = 4, and a[left] = 8, a[right] = 5
Area = min(a[left], a[right]) * (right - left) = min(8, 5) * (4 - 1) = 12
maxArea = max(maxArea, Area) = max(56, 12) = 56

At left = 2, right = 4, and a[left] = 6, a[right] = 5
Area = min(a[left], a[right]) * (right - left) = min(6, 5) * (4 - 2) = 10
maxArea = max(maxArea, Area) = max(56, 10) = 56

At left = 2, right = 3, and a[left] = 6, a[right] = 2
Area = min(a[left], a[right]) * (right - left) = min(6, 2) * (3 - 2) = 2
maxArea = max(maxArea, Area) = max(56, 2) = 56

At left = 3, right = 3, and a[left] = 2, a[right] = 2
Area = min(a[left], a[right]) * (right - left) = min(2, 2) * (3 - 3) = 0
maxArea = max(maxArea, Area) = max(56, 0) = 56

At left = 4, right = 3, and a[left] = 5, a[right] = 2
Area = min(a[left], a[right]) * (right - left) = min(5, 2) * (2 - 4) = 0
maxArea = max(maxArea, Area) = max(56, 0) = 56

At left = 5, right = 3, and a[left] = 4, a[right] = 2
Area = min(a[left], a[right]) * (right - left) = min(4, 2) * (2 - 5) = 0
maxArea = max(maxArea, Area) = max(56, 0) = 56

At left = 6, right = 3, and a[left] = 8, a[right] = 2
Area = min(a[left], a[right]) * (right - left) = min(8, 2) * (2 - 6) = 0
maxArea = max(maxArea, Area) = max(56, 0) = 56

At left = 7, right = 3, and a[left] = 3, a[right] = 2
Area = min(a[left], a[right]) * (right - left) = min(3, 2) * (2 - 7) = 0
maxArea = max(maxArea, Area) = max(56, 0) = 56

At left = 8, right = 3, and a[left] = 7, a[right] = 2
Area = min(a[left], a[right]) * (right - left) = min(7, 2) * (2 - 8) = 0
maxArea = max(maxArea, Area) = max(56, 0) = 56

The pointers meet at left = right = 3, and the traversal ends.

Step 4: Return maxArea as the final answer.

Therefore, the maximum area of the container is 56.

Time Complexity: The time complexity of the above algorithm is O(n), where n is the length of the input array.

Space Complexity: The space complexity of the above algorithm is O(1), as we are not using any extra space.

Thus, we have successfully solved the Container With Most Water problem on LeetCode using the two-pointer approach.

Step by Step Implementation For Container With Most Water

/**
 * @author: Jiawei Wu
 * @create: 2020-03-15 10:34
 *
 * Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) 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
 **/

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int left = 0;
        int right = height.length - 1;

        while (left < right) {
            int area = Math.min(height[left], height[right]) * (right - left);
            maxArea = Math.max(maxArea, area);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }
}

def maxArea(self, height: List[int]) -> int:
        # set up two pointers, left and right, at the beginning and end of the array
        left = 0
        right = len(height) - 1
        
        # initialize max area to 0
        max_area = 0
        
        # while the left pointer is less than the right pointer,
        # calculate the area between them and update max_area if necessary
        while left < right:
            # to calculate area, take the smaller height of the two
            # and multiply it by the distance between the two pointers
            h = min(height[left], height[right])
            area = h * (right - left)
            
            # update max_area if necessary
            max_area = max(max_area, area)
            
            # move the pointer with the smaller height towards the other one
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        
        # return the max area
        return max_area

var maxArea = function(height) {
  // we will keep track of the max area
  let max = 0;
  // we will use two pointers, one at the beginning and one at the end of the array
  let left = 0;
  let right = height.length - 1;
  // as long as the left pointer is less than the right pointer
  while (left < right) {
    // we find the area by taking the smaller height and multiplying it by the distance between the two pointers
    let area = Math.min(height[left], height[right]) * (right - left);
    // we update the max area if the current area is greater than the max area
    if (area > max) {
      max = area;
    }
    // if the height at the left pointer is less than the height at the right pointer, we move the left pointer up one
    // this is because we want to find a greater height to see if we can get a greater area
    if (height[left] < height[right]) {
      left++;
    }
    // otherwise, we move the right pointer down one
    else {
      right--;
    }
  }
  // return the max area
  return max;
};

class Solution {
public:
    int maxArea(vector& height) {
        
        //initialize two pointers, one at the beginning and one at the end of the vector
        int left = 0;
        int right = height.size() - 1;
        
        //initialize maxArea to be the area of the container between the first and last element
        int maxArea = (right - left) * min(height[left], height[right]);
        
        //while the left pointer is less than the right pointer, 
        while (left < right) {
            
            //if the height of the left element is less than the height of the right element
            if (height[left] < height[right]) {
                
                //increment the left pointer
                left++;
                
                //compare the area of the new container with the maxArea
                //replace maxArea if the new area is greater
                maxArea = max(maxArea, (right - left) * min(height[left], height[right]));
                
            //if the height of the left element is greater than or equal to the height of the right element    
            } else {
                
                //decrement the right pointer
                right--;
                
                //compare the area of the new container with the maxArea
                //replace maxArea if the new area is greater
                maxArea = max(maxArea, (right - left) * min(height[left], height[right]));
            }
        }
        
        //return the maxArea
        return maxArea;
    }
};

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;
}