Container With Most Water

The Container With Most Water is a classic problem in algorithmic and computational thinking, that is often used to test the efficiency and problem-solving skills of developers.

The problem statement is as follows:

You are given a list of n non-negative integers, where each integer represents a vertical line at position i with a height of height[i]. The width of each vertical line is 1. Find two lines, which, together with the x-axis, forms a container that contains the most water.

In other words, you need to find two vertical lines in the list that create the largest possible rectangle with the x-axis. The area of the rectangle represents the amount of water that the container can hold.

For example, consider the following input list of heights:

heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]

The figure below shows the list of heights as vertical lines, and the largest container that can be formed by selecting the lines at indices 1 and 8 (highlighted in red). The area of this container is 49 (7×7).

              |          
        |     |          
        |     |          
        |     |     |    
  |     |     |     |    
  |     |     |     |    
  |     |     |     |  | 
--|-----|-----|-----|--|
  1     8     6     2  5  4  8  3  7

In this case, selecting any other pair of lines would result in a smaller container.

Here are three approaches to solve the Container With Most Water problem, along with their pseudocode and explanations:

Approach 1: Brute Force

One simple approach to solving this problem is to use a brute force approach, which involves comparing every pair of lines and finding the one with the largest container.

max_area = 0
for i = 0 to n-1 do
  for j = i+1 to n-1 do
    area = (j - i) * min(height[i], height[j])
    max_area = max(max_area, area)
return max_area

We use a nested loop to iterate over every possible pair of lines. For each pair of lines, we calculate the area of the container that they form by multiplying the difference in their indices by the minimum height between them.

We then update a variable max_area with the maximum area we have found so far. Finally, we return max_area.

The time complexity of this approach is O(n^2), because we visit each pair of lines exactly once.

Approach 2: Two-Pointer Approach

A more efficient approach to solving this problem is to use the two-pointer approach.

max_area = 0
left = 0
right = n-1
while left < right do
  area = (right - left) * min(height[left], height[right])
  max_area = max(max_area, area)
  if height[left] < height[right] then
    left = left + 1
  else
    right = right - 1
return max_area

We start with two pointers, one at the beginning of the list (left) and one at the end (right). We then calculate the area of the container formed by these two lines, and update max_area with the maximum area we have found so far.

We then move the pointer with the smaller height inward (i.e., if height[left] < height[right], we move the left pointer to the right, otherwise we move the right pointer to the left). We repeat this process until the left and right pointers meet in the middle of the list.

The time complexity of this approach is O(n), since we visit each element in the list exactly once.

Approach 3: Using Stack

Another approach is to use a stack to keep track of the indices of the lines in the list. We can use the stack to keep track of the lines that might be useful in forming a larger container.

max_area = 0
stack = []
for i = 0 to n-1 do
  while stack is not empty and height[i] > height[stack.top()] do
    top = stack.pop()
    if stack is not empty then
      width = i - stack.top() - 1
    else
      width = i
    area = width * height[top]
    max_area = max(max_area, area)
  stack.push(i)
while stack is not empty do
  top = stack.pop()
  if stack is not empty then
    width = n - stack.top() - 1
  else
    width = n
  area = width * height[top]
  max_area = max(max_area, area)
return max_area

We start by initializing an empty stack. We then iterate through the list of heights. For each height, we check if the height is greater than the height at the top of the stack. If it is, we pop the top element from the stack and calculate the area of the container that

The two-pointer approach is generally considered to be the best approach for solving the Container With Most Water problem, because it has a time complexity of O(n), which is optimal for this problem.

The brute force approach has a time complexity of O(n^2), which is not efficient and will not work for large input sizes. The stack-based approach also has a time complexity of O(n), but it has higher constant factors and uses more memory than the two-pointer approach.

In addition, the two-pointer approach is simpler to understand and implement than the stack-based approach, and it does not require any additional data structures.

Therefore, the two-pointer approach is the recommended approach for solving the Container With Most Water problem.

Container With Most Water: Java 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;
}

Container With Most Water: JavaScript Solution

function maxArea(height) {
    let maxArea = 0;
    let left = 0;
    let right = height.length - 1;
    
    while (left < right) {
        const area = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, area);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxArea;
}

Container With Most Water: Python Solution

def maxArea(height):
    maxArea = 0
    left = 0
    right = len(height) - 1
    
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        maxArea = max(maxArea, area)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return maxArea

Container With Most Water: Ruby Solution

def max_area(height)
    max_area = 0
    left = 0
    right = height.length - 1
    
    while left < right
        area = [height[left], height[right]].min * (right - left)
        max_area = [max_area, area].max
        if height[left] < height[right]
            left += 1
        else
            right -= 1
        end
    end
    
    return max_area
end

The general idea behind the two-pointer approach is to use two pointers to explore the solution space in a more efficient way than brute force.

In the case of the Container With Most Water problem, we can use two pointers left and right to represent the two lines that form the container.

We start with left at the beginning of the list and right at the end of the list. We calculate the area of the container formed by these two lines using the formula:

area = (right - left) * min(height[left], height[right])

We then update a variable maxArea with the maximum area we have found so far, and then move the pointer with the smaller height inward. We repeat this process until the pointers meet in the middle of the list.