Container with Most Water In Javascript

three sum algorithm

Container With Most Water is the most frequently asked interview question in Big Tech Companies.

Here is the detailed Question:

Given n non-negative integers a_1, a_2, ..., a_n         where each represents a point at coordinate (i, a_i)         . ‘ n ‘ vertical lines are drawn such that the two endpoints of line i is at (i, a_i)         and (i, 0)         .
Find two lines, which together with x-axis forms a container, such that the container contains the most water.
The program should return an integer which corresponds to the maximum area of water that can be contained (maximum area instead of maximum volume sounds weird but this is the 2D plane we are working with for simplicity).

Read more:

Face to Face Interview Questions and Answers

Interview Brain Teasers

You can checkout the Visual representation of Given Array Below.

Example 1:

Container with Most Water
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]. In this case, the max area of water (blue section) the container can contain is 49.

Here is the equation to find Area of the container.

Area = height of lower wall * width.

width = distance between indices of two elements.

height is the given value of elements.

We will start with the first element of the array and last element of the array and find out the area.

First element = 1
Lat element = 7

width = index of the last element - index of the first element

width = 8 - 0 = 8

Area = 1 * 8 => 8

Now 1 is lower than 7 so we will move to second element and keep last element and calculate the area.

If we find last element is lower than first element then we move to second last element and keep first element as is.

We can perform these steps through loop and find out the maximum area.

Example 2:  

Input: array = [1, 5, 4, 3] 

Output: 6 

Explanation :  5 and 3 are distance 2 apart.  So the size of the base = 2. Height of container = min(5, 3) = 3.  So total area = 3 * 2 = 6 

Example 3:  

Input: array = [3, 1, 2, 4, 5] 

Output: 12 

Explanation :  5 and 3 are distance 4 apart.  So the size of the base = 4.  Height of container = min(5, 3) = 3.  So total area = 4 * 3 = 12 

Solution for Container with Most Water

Here is executable working solution in Javascript.

const maxArea = (arr) => {
  let i = 0;
  let j = arr.length - 1;
  let area = 0;
   while (i < j) {
     area = Math.max(area, Math.min(arr[i], arr[j]) * (j - i));
     
     if (arr[i] < arr[j]) {
       i += 1
     } else {
       j -= 1
     }
   }
   return area;
}