:orphan:

Container With Most Water
=========================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/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``` 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.

 

**Example 1:**

|image1|

::


   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.

**Example 2:**

::


   Input: height = [1,1]
   Output: 1

 

**Constraints:**

- ``n == height.length``
- ``2 <= n <= 10``\ :sup:```5```
- ``0 <= height[i] <= 10``\ :sup:```4```

.. |image1| image:: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/07/17/question_11.jpg

.. highlight:: python

Pattern
-------
Array, Two Pointers, Greedy

Solution
--------
Since the area of a container is the product of its width and height, set the
``left`` and ``right`` pointer to ends. Compute the area and store it as the
``max_area``. Then, move the pointer with the smaller height inwards. If the
heights are equal, move the pointer whose inward height is larger.

Code
----

.. literalinclude:: ../problems/medium/container-with-most-water/container_with_most_water__approach_1.py
    :language: python
    :lines: 9-

Test
----
>>> from container_with_most_water__approach_1 import maxArea
>>> maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])
49
>>> maxArea([1, 1])
1

Complexity
----------
| :math:`n` is the length of the input array
| Time: :math:`O(n)` — single pass with two pointers
| Auxiliary Space: :math:`O(1)`

.. autofunction:: container_with_most_water__approach_1.maxArea