Solutions

For each container the area is calculated by the formula:

$area = min(lines[i], lines[j]) * (j - i)$

$j$ and $i$ are indexes of two elements in the array
$j - i$ is the width of the container
$min(lines[i], lines[j])$ is the height of the container

1. Brute Force

O(n²) time | O(1) space

Intuition

We can calculate every possible container's area, keeping the largest one.

To get all the possible containers we will use two nested loops over the whole array.

Algorithm

Create a largest_area integer variable.
Iterate through the outer loop from the first element to the last element with i index.
For each outer loop iteration, iterate through the inner loop from the element at i + 1 to the last element with j index.
Calculate the area of a container formed by two elements on i and j indexes and update largest_area if the value is greater.

012345

i j

area = 1 * 2 = 2, largest_area = 2

1 / 16

Code

def maxArea(lines: list[int]) -> int:
    largest_area = 0
    for i in range(len(lines)):
        for j in range(i + 1, len(lines)):
            width = j - i
            height = min(lines[i], lines[j])
            area = width * height
            largest_area = max(area, largest_area)
    return largest_area

/**
 * @param {number[]} lines
 * @returns {number}
 */
var maxArea = function (lines) {
  let largestArea = 0
  for (let i = 0; i < lines.length; i++) {
    for (let j = i + 1; j < lines.length; j++) {
      const width = j - i
      const height = Math.min(lines[i], lines[j])
      largestArea = Math.max(largestArea, width * height)
    }
  }
  return largestArea
}

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

2. Two Pointers

O(n) time | O(1) space

Intuition

We can use one loop with two indexes starting at each side of the array.

We calculate the area of a container formed by those indexes, then move only one of the two indexes.

If the left element is less than the right element, we can skip the left element completely as pairing the left element with any other element can only form a smaller container as both width and height can only decrease.

In the same way we can skip the right element if it is less than the left element.

Algorithm

Create a largest_area integer variable.
Set the left index to the first element and the right index to the last element.
Iterate through the loop while left is less than right.
- Update largest_area if the area of a container formed by two elements on those indexes is greater.
- If the left element is less than the right, move left index to the right left = left + 1.
- If the left element is greater than the right, move right index to the left right = right - 1.

012345

lo hi

area = 5 * 2 = 10, largest_area = 10

1 / 6

Code

def maxArea(lines: list[int]) -> int:
    left, right, largest_area = 0, len(lines) - 1, 0
    while left < right:
        width = right - left
        height = min(lines[left], lines[right])
        area = width * height
        largest_area = max(largest_area, area)

        if lines[left] < lines[right]:
            left += 1
        else:
            right -= 1
    return largest_area

/**
 * @param {number[]} lines
 * @returns {number}
 */
var maxArea = function (lines) {
  let left = 0, right = lines.length - 1, largestArea = 0
  while (left < right) {
    const width = right - left
    const height = Math.min(lines[left], lines[right])
    largestArea = Math.max(largestArea, width * height)
    if (lines[left] < lines[right]) left++
    else right--
  }
  return largestArea
}

class Solution {
    public int maxArea(int[] lines) {
        int left = 0;
        int right = lines.length - 1;
        int largestArea = 0;
        while (left < right) {
            int width = right - left;
            int height = Math.min(lines[left], lines[right]);
            largestArea = Math.max(largestArea, width * height);
            if (lines[left] < lines[right]) left++;
            else right--;
        }
        return largestArea;
    }
}