C++ Program to Find Container With Most Water














































C++ Program to Find Container With Most Water



Container With Most Water

Given N non-negative integers a1,a2,....an where each represents a point at coordinate (i, ai). N vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i,0). Find two lines, which together with x-axis forms a container, such that it contains the most water.

Approach: We will use the concept of sliding window to find the max area, we use two pointers hi and lo, the hi will be pointing toward the end of array and lo will be at starring of array. we find the area using the given formula = (hi-lo)*abs(array[hi]-array[lo]) store it some variable. if element at position hi is greater than that of position lo we increment lo else we decrement hi.

Time Complexity:O(n)
Space Complexity:O(1)

Code :
#include<bits/stdc++.h>
using namespace std; long long maxArea(long long A[], int len)
{
long long hi = len-1, lo = 0, area, ans = 0;
while(hi > lo){ area = (hi-lo)*min(A[hi], A[lo]); ans = max(ans, area ); ( A[hi] > A[lo]) ? lo++ : hi--; }
return ans; } int main(){
int arr[] = {1,5,4,3};

int n = sizeof(arr)/arr[0];
cout << maxarea(arr, n) << endl;
return 0; }


Output 6


Comments