Container With Most Water

DevSniper
Published : 03 August 2024

165 Views

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]). Your goal is to find two lines that, along with the x-axis form a container that can hold the maximum amount of water Return the maximum amount of water a container can store.

Example 1 :-

[2,8,6,5,5,4,8,4,7]

Output : 49

Example 2 :-

[5, 3, 2, 4, 15]

Output : 20

Constraints :

n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4
You may not slant the container.

Brute Force (Naive) Approach

Idea behind this approach involves examining every possible pair of lines to determine which pair can trap the maximum amount of water. To do this, you would calculate the water volume trapped by each pair of lines and keep track of the highest volume found. Here is a step-by-step breakdown of this approach

Steps :

Declare and initialize a variable to track maximum area of water. max_area with MIN VALUE
Use two nested loops to iterate over all possible pairs of lines. The outer loop picks the first line and the inner loop picks the second line.
For each pair of lines, compute the area of the container they create with the x-axis.
If the current pair area is greater than max_area then update max_area.
After completing the iteration max_area will hold the maximum amount of water that can be trapped by any pair of lines.

C++

Java

Python

#include <bits/stdc++.h>
using namespace std;

int maxArea(int arr[], int n)
{
    int max_area= INT_MIN;
    for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            max_area = max(max_area, min(arr[i], arr[j])*(j-i));
        }
    }
    return max_area;
}
int main()
{
    int arr[] = {2, 8, 6, 5, 5, 4, 8, 4, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxArea(arr,n);
}

Time Complexity : O(N^2)

Space Complexity : O(1)

Using Two Pointers (Optimal Approach)

The approach can be optimized using a two-pointer technique. The area is determined by the formula min(arr[i], arr[j]) * (j - i), where i and j are indices of the lines, and j - i represents the width of the container. To maximize the area, we need to focus on Maximizing both width and height.

For maximizing the width (j - i) we start with pointers i at the beginning (0) and j at the end (n - 1) of the array. And for Maximizing Height If arr[i] is less than arr[j], increment i otherwise decrement j.

Steps :

Declare and initialize variables max_area with MIN VALUE i =0 and j= arr.length -1
Iterate until i less than j
if new area (formula min(arr[i],arr[j])*(j-i)) if greater than max_area update max_area
if arr[i] is greater than arr[j] increment i otherwise decrement j.
After completing the iteration max_area will hold the maximum amount of water that can be trapped by any pair of lines.

C++

Java

Python

#include <bits/stdc++.h>
using namespace std;

int maxArea(int arr[], int n)
{
    int max_area= INT_MIN;
    int i=0,j=n-1;
    while(i<j) {
        max_area = max(max_area, min(arr[i],arr[j])*(j-i));
        if(arr[i]<arr[j]) {
            i++;
        } else {
            j--;
        }
    }
    return max_area;
}
int main()
{
    int arr[] = {2, 8, 6, 5, 5, 4, 8, 4, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxArea(arr,n);
}

Time Complexity : O(N)

Space Complexity : O(1)