Relevant

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.

Example:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

Explanation: 

  8 │     █
  7 │     █                    █
  6 │     █  █                 █
  5 │     █  █        █        █
  4 │     █  █        █  █     █
  3 │     █  █        █  █     █
  2 │     █  █  █     █  █  █  █
  1 │  █  █  █  █  █  █  █  █  █
    └──────────────────────────────
       0  1  2  3  4  5  6  7  8
          ↑                    ↑
        height 8             height 7
          │←──── width = 7 ────→│
          └─────────────────────┘

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 the container can contain is 49.

Solve Here: Leetcode 11

Basic Intuition

Two vertical lines of height h1 and h2, separated by a distance of d, can hold a maximum of min(h1, h2) * d units of water.

Approach 1: Nested Loops

Use two nested loops to iterate over all possible pairs of vertical lines and calculate the area of the container formed by the two lines and the x-axis. Keep track of the maximum area found.

Algorithm

1int maxArea(int[] height) {

2int maxArea = 0;

3for (int i = 0; i < height.length; i++) {

4for (int j = i + 1; j < height.length; j++) {

5int width = j - i;

6int minH = Math.min(height[i], height[j]);

7int area = minH * width;

8maxArea = Math.max(maxArea, area);

10}

11return maxArea;

12}

Input

i—j—width—minH—area—maxArea0

Time Complexity

Since we are iterating over all n * (n - 1) / 2 pairs of vertical lines, the overall time complexity will be of the order O(n^2).

Space Complexity