আমাদের কন্টেইনারের দেওয়ালের উচ্চতা দিয়ে একটি অ্যারে দেওয়া আছে। লক্ষ্য হলো সর্বোচ্চ পানি ধারণকারী কন্টেইনার বের করা। দুটি দেওয়ালের মধ্যে দূরত্ব (width) = j - i (0 <= i < j <= N)। পানির উচ্চতা = দুটি দেওয়ালের ন্যূনতম। অর্থাৎ Area = min(Arr[i], Arr[j]) * (j - i)। এই এরিয়ার সর্বোচ্চ করা উচিত।
ইনপুট
Arr[]= { 5,1,2,3,5 }
আউটপুট
Maximum water area : 20
ব্যাখ্যা: Arr[0]=5 এবং Arr[4]=5, width=4, area=5*4=20 (সর্বোচ্চ)।
ইনপুট
Arr[]= { 1, 5, 4, 3, 2, 4 }
আউটপুট
Maximum water area : 16
ব্যাখ্যা: Arr[1]=5 এবং Arr[5]=4, width=4, area=4*4=16 (সর্বোচ্চ)।
প্রোগ্রামে ব্যবহৃত পদ্ধতি (Two Pointer)
- walls[] অ্যারে দিয়ে হাইট স্টোর।
- mostwater(int A[], int len) ফাংশন এরিয়া রিটার্ন করে।
- দুটি পয়েন্টার: l=0 (বাম), r=len-1 (ডান)।
- area, maxarea = 0।
- while (l < r): lwall=A[l], rwall=A[r], minwall=min(lwall, rwall)।
- area = minwall * (r-l)। maxarea আপডেট।
- যদি lwall < rwall হয় তবে l++ অন্যথায় r-- (ছোট দেওয়ালটি মুভ করা)।
- maxarea রিটার্ন।
উদাহরণ কোড
#include <iostream>
using namespace std;
int mostwater(int A[], int len){
int r = len-1, l = 0;
int area = 0, maxarea = 0;
while (l < r){
int lwall = A[l];
int rwall = A[r];
int minwall = min(lwall, rwall);
area = minwall * (r - l);
maxarea = max(maxarea, area);
if (lwall < rwall)
l++;
else
r--;
}
return maxarea;
}
int main(){
int walls[] = {1, 5, 4, 3, 2, 4};
int num = sizeof(walls) / sizeof(walls[0]);
cout << "Container with Most water has area:" << mostwater(walls, num);
return 0;
}আউটপুট
Container with Most water has area:16
