Container with Most Water

Container with Most Water

Blind 75. Array Question

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

Real world applications:

1. Resources Allocation:
2. Logistics:
3. It could be used to optimize how to pack items of varying heights into containers
4. Urban planning:
5. To design optimal layouts for building or parking lots
6. VR space:
7. Determining optimial viewing areas in virtual environments.
8. Netflix:
9. Algorithms to maximize user watch time within available content

These are some real world problems that can be solved using the solution of container with max water. Let's see how we can solve it?

What are obvious conclusions given from question?

    sliding window technique:

1. Calculate max water that can fit in container with max wall
2. we need to calculate height of wall * breadth of wall
3. thus, we need to find area
4. height is given from heights[i],whereas breadth is given from index position
5. we need two pointers to compare two walls
6. when to move what pointers?
7. smaller walls pointer gets moved as we need to calculate max

  function maxWater(heights){

  let maxArea = 0

  let l = 0

  let r = heights.length - 1

  while(l < r){

    let height = Math.min(heights[l], heights[r])

    let breadth = r - l

    maxArea = Math.max(maxArea, height * breadth)

    if(heights[l] < heights[r]){

      l++

    }else{

      r--

    }

  }

  return maxArea

}

This is how this problem can be solved.

Complexity:

Time complexity is O(n), as we are iterating through the array once

Space complexity is O(1), as we don't have any array or storage