11. leetcode solution using JavaScript

11. Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i<sup>th</sup> 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.

Notice that you may not slant the container.

Let's understand the question in simple words:

Imagine you have vertical lines of different heights, and you want to find the largest possible rectangular container that can be formed between two lines. This is the classic "Container With Most Water" problem.

Let's look at how to solve this efficiently in JavaScript.

Example 1:

Way 1: The Brute Force Approach

One simple way is to check every pair of lines. Calculate the area for each, keep track of the max.

But this becomes very inefficient for large inputs, taking O(N^2) time to check every combination.

Way 2: A Faster Approach - Two Pointers

A better approach uses two pointers initialized to both ends of the array of heights.

Here is one way to solve this using the Two Pointer Technique:

var maxArea = function(height) {
  let n = height.length;
  let maxArea = 0;
  let left = 0;   //starting of array
  let right = n - 1; // end of array

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

     // Move pointer at shorter line
    if (height[left] < height[right]) {
      left++; 
    } else {
      right--;
    }
    //update max
    maxArea = Math.max(maxArea, area);
  }

  return maxArea;
};

How it work :

Let's put this approach to the test with an example. Consider the array height = [1, 8, 6, 2, 5, 4, 8, 3, 7].

1. We start with left at position 0 and right at position 8.

2. The initial container's width is 8 - 0 = 8, and the height is min(1, 7) = 1. So, the initial maxArea is 8 * 1 = 8.

3. Since the left side has a smaller height (1), we move the left pointer to the right (i.e., left = 1).

4. Now, the container's width is 7 - 1 = 6, and the height is min(8, 7) = 7. So, the updated maxArea is 6 * 7 = 42.

5. We continue this process, alternating between moving the left and right pointers, recalculating the area, and updating maxArea.

6. After exploring all possible configurations, we find that the maximum water capacity is 49.