PROBLEM LINK:
Author: Sandeep Singh
Tester: Arnab Chanda
DIFFICULTY:
Easy
PREREQUISITES:
None but idea of two pointers will help.
EXPLANATION:
This problem is the same as the famous water container problem. The area is decided by the distance between the 2 lines selected and the height of the smaller of these 2 lines. Let’s take 2 pointers lft and rgt pointing to the extreme left and extreme right lines respectively. At tis moment, the base is the max possible. Now we will decrease the base in order to get a better heigth if possible.
The question is which pointer to move. We move the one with the smaller height. why? Remember that area is also restricted by the smaller of the 2 lines. so if we move the one with the greater height, the height of the rectangle still remains same or rather might even decrease. So to make the movement beneficial, we move the one with smaller height.
We do this while lft is smaller than rgt. And at each step we calculate the area and store the max area formed.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define ll long long int
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define scanarr(a,b,c) for(int i=b;i<c;i++)cin>>a[i]
#define showarr(a,b,c) for(int i=b;i<c;i++)cout<<a[i]<<' '
#define ln cout<<'\n'
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mod 1000000007
using namespace std;
////////////////////////////////////////////////////////////////CODE STARTS HERE////////////////////////////////////////////////////////////////
int maxArea(vector<int>& height) {
int n = height.size();
int left, right;
left = 0;
right = n-1;
int ans = 0;
int tmp;
while(left<right){
tmp = min(height[left], height[right]) * (right - left);
ans = max(ans, tmp);
if(height[left] < height[right])
left++;
else
right--;
}
return ans;
}
int main(){
int t;
cin>>t;
int N, M;
while(t--){
int n;
cin>>n;
vector<int> h(n);
for(int i=0;i<n;i++)
cin>>h[i];
cout<<maxArea(h)<<endl;
}
}
Tester's Solution
def maxArea(height) -> int:
left = 0
right = len(height)-1
area = k= 0
while(left<right):
width = right-left
area = max(area,width*min(height[left],height[right]))
#print(width*min(left,right))
if height[left]>height[right]:
right-=1
else:
left+=1
return area
test = int(input())
for _ in range(test):
n = int(input())
arr = [int(x) for x in input().split()]
print(maxArea(arr))
Time complexity is O(N)