Arrays - 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^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.

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 (two red poles connected with a line) the container can contain is 49.

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

Constraints:

n == height.length
2 <= n <= 10⁵
0 <= height[i] <= 10⁴

Solution 1 - Using two pointers, compute area between two heights and keep track of maximum area

In this approach, we are going to use two pointers on both sides of height array, and calculate area between two height poles, and keep track of maximum area.

Implementation steps:

First, we will two variables left, and right to point both ends of height array, and another variable maxArea to keep track of maximum area.
Then, we will compute the area between the heights at left and right pointers, using area = MIN(height_left, height_right) * width ( here, width is the difference between two pointers right and left).
Now, compare area with maxArea, if current area is greater, then update maxArea with current area.
Now, when updating left or right pointers, since we can hold the water until the minimum height among two heights, move the smallest one inorder to check if there is any bigger height:
- If the height[left] is smaller than height[right], then increment left pointer.
- Otherwise, decrement right pointer.
Finally, return maxArea.

public class ContainerWithMostWater { static int maxArea(int[] height) { int left = 0; int right = height.length - 1; int maxArea = 0; while (left < right) { int area = Math.min(height[left], height[right]) * (right - left); maxArea = Math.max(area, maxArea); if (height[left] < height[right]) { left++ ; } else { right--; } } return maxArea; } public static void main(String[] args) { System.out.println(maxArea(new int[]{1,8,6,2,5,4,8,3,7})); System.out.println(maxArea(new int[]{1,1})); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time, where n is the length of input array height.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: