LeetCode Problem #11: Container With Most Water - Explanation and Solutions in Python and JavaScript

Introduction

The Container With Most Water problem is a classic problem that tests your understanding of the two-pointer technique and array manipulation. It is frequently asked in coding interviews to assess your problem-solving skills. In this post, we'll break down the problem, explain the optimal approach, and provide solutions in both Python and JavaScript.

Problem Statement

Given an array of integers height of length n, where each element represents a vertical line at position i with height height[i], find two lines that together with the x-axis form a container that holds the most water.

Return the maximum amount of water a container can store.

Example:

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Explanation: The above vertical lines are represented by array [1, 8, 6, 2, 5, 4, 8, 3, 7]. The container with the most water is formed by the lines at positions 1 and 8 (height = 7 and 8). The area is min(7, 8) * (8 - 1) = 49.
    

Approach

The problem can be solved efficiently using the **two-pointer technique**. Here's the step-by-step approach:

1. Initialize two pointers, left at the start of the array and right at the end.
2. Calculate the area formed by the lines at left and right.
3. Move the pointer pointing to the shorter line inward, as moving the longer line cannot increase the area.
4. Repeat the process until the pointers meet.
5. Keep track of the maximum area found during the process.

Solution in Python

def maxArea(height):
    left, right = 0, len(height) - 1
    max_area = 0

    while left < right:
        area = min(height[left], height[right]) * (right - left)
        max_area = max(max_area, area)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_area
        

Explanation: We use two pointers to calculate the area formed by the lines at the current positions. We move the pointer pointing to the shorter line inward and keep track of the maximum area found.

Solution in JavaScript

function maxArea(height) {
    let left = 0, right = height.length - 1;
    let maxArea = 0;

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

        if (height[left] < height[right]) {
            left