কনটেন্টে যান

012 — Container With Most Water

Problem link ও উৎস

  • Original source: Classic converging two-pointer exercise
  • Platform: LeetCode — https://leetcode.com/problems/container-with-most-water/
  • Topic: array / two pointers
  • Difficulty: Medium
  • Pattern: two pointers (দুই প্রান্ত থেকে, ছোট দেয়াল discard)
  • Basic idea inherited from: pair-sum-এর discard argument — প্রতিটা move-এ একটা candidate চিরতরে বাদ দেওয়া যায় বলে O(n)

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা array height দেওয়া, যেখানে height[i] হলো i-তম খাড়া দেয়ালের উচ্চতা (সব দেয়ালের মধ্যে দূরত্ব 1)। দুটো দেয়াল বেছে তাদের মধ্যে পানি ধরলে কত পানি ধরে = min(দুই দেয়ালের উচ্চতা) * (দুই দেয়ালের মধ্যে দূরত্ব)। সবচেয়ে বেশি কত পানি (area) ধরা সম্ভব, সেটা বের করো।

উদাহরণ
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
index 1 (উচ্চতা 8) আর index 8 (উচ্চতা 7) -> min(8,7) * (8-1) = 7 * 7 = 49

Input ও output

উদাহরণ
Input : [1, 8, 6, 2, 5, 4, 8, 3, 7] -> 49
Input : [1, 1]                       -> 1

Edge case 1 (সমান উচ্চতা): [4, 3, 2, 1, 4] -> 16  (দুই প্রান্তের 4, width 4)
Edge case 2 (ছোট):         [1, 2, 1]       -> 2

চেনা উদাহরণে বোঝা

ভাবো দুজন দুই প্রান্তে দাঁড়িয়ে একটা চাদর ধরে পানি ধরার চেষ্টা করছে। যে কম উঁচুতে ধরে আছে, পানি তো তার উচ্চতাতেই উপচাবে। তাই যে নিচে ধরে আছে সে-ই এক ঘর ভেতরে এসে আরও উঁচু জায়গায় ধরার চেষ্টা করুক — উঁচু জনকে সরালে শুধু চাদরই ছোট হবে, লাভ নেই।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

ভিত two pointers-এর discard argument: দুই প্রান্ত থেকে শুরু করো, আর প্রতিটা step-এ এমনভাবে এক pointer সরাও যাতে কোনো সম্ভাব্য সেরা উত্তর হারিয়ে না যায়। pair-sum-এ "L বাড়ালে sum বাড়ে, R কমালে sum কমে" যেমন; এখানে "ছোট দেয়াল সরালে কিছুই হারাই না"। দুই-pointer-এর math যুক্তি ../../01-math-based-programming-fundamentals/06-two-pointers-sliding-window-math/-তে।

ভেতরের যুক্তি

লুকানো logic: area = min(h[L], h[R]) * (R - L)। দুই প্রান্ত থেকে শুরুতে width সবচেয়ে বড়। এখন ছোট দেয়ালটা সরানোই যুক্তিযুক্ত — কারণ সেই ছোট দেয়াল ধরে রাখলে width তো কমবেই, আর উচ্চতাও ওই ছোট দেয়ালেই আটকে; তাই ছোট দেয়াল ফেলে দিলে কোনো বড় উত্তর হারানোর ভয় নেই। বড় দেয়াল সরালে উল্টো ভালো জোড়া হারাতে পারতাম।

কী দিয়ে তথ্য রাখব

কোনো extra data structure লাগে না — শুধু দুটো integer pointer (left, right) আর একটা best। O(1) extra space।

এটি কেন উপযুক্ত

Array-র O(1) random access-এ height[left] আর height[right] সাথে সাথে পড়া যায়। দুই প্রান্ত থেকে ভেতরে আসা two-pointer scan-এ প্রতিটা index একবারই ছোঁয়া হয়, তাই সব O(n^2) জোড়া না দেখেও সেরা area পাওয়া যায়।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: প্রতিটা জোড়া দেয়াল (i, j) ধরে area হিসাব করে সবচেয়ে বড়টা রাখো — দুটো nested loop।

উদাহরণ
best = 0
for i in range(n):
    for j in range(i+1, n):
        area = min(height[i], height[j]) * (j - i)
        best = max(best, area)

কোথায় বেশি কাজ হচ্ছে

দুটো nested loop মানে প্রায় n*(n-1)/2 জোড়া — O(n^2)। array বড় হলে খুব ধীর। অথচ দুই প্রান্ত থেকে শুরু করে প্রতিটা step-এ ছোট দেয়াল ফেলে দিলে এক pass-এই সেরা area পাওয়া যায়।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: দুই প্রান্তের জোড়ায় width সর্বোচ্চ। এখান থেকে ছোট দেয়াল সরালে সম্ভাব্য সেরা উত্তর হারানো যায় না (ছোট দেয়াল ধরে রাখলে height ওতেই সীমিত, width-ও কমবে)। তাই প্রতিটা step একটা দেয়াল চিরতরে বাদ দেয় — n step-এ শেষ।

আরও কম কাজে সমাধান

left=0, right=n-1। যতক্ষণ left < right: এখনকার area (min(h[left],h[right]) * (right-left)) দিয়ে best update করো, তারপর যে প্রান্তের দেয়াল ছোট সেটা ভেতরে সরাও (সমান হলে যেকোনো একটা)। ওরা দেখা করলেই শেষ। এক pass, O(n)।

ভাবনার পরিবর্তন

মোচড়: "সব জোড়া try করব" (O(n^2)) ভুলে গিয়ে ভাবো "দুই প্রান্ত থেকে শুরু করব, সবসময় ছোট দেয়ালটা ফেলে ভেতরে আসব।" ছোট দেয়াল-ই bottleneck, তাই সেটা সরানোই একমাত্র যুক্তিসঙ্গত move।

ছবিতে বোঝা

height = [1, 8, 6, 2, 5, 4, 8, 3, 7] দিয়ে দুই pointer:

উদাহরণ
L=0(1)  R=8(7): area = min(1,7)*8 = 8 ;  h[L]<h[R] -> L++
L=1(8)  R=8(7): area = min(8,7)*7 = 49;  h[L]>=h[R]-> R--   best 49
L=1(8)  R=7(3): area = min(8,3)*6 = 18;  R--
L=1(8)  R=6(8): area = min(8,8)*5 = 40;  R--
L=1(8)  R=5(4): area=4*4=16; R--
L=1(8)  R=4(5): area=5*3=15; R--
L=1(8)  R=3(2): area=2*2=4; R--
L=1(8)  R=2(6): area=6*1=6; R--
L=R=1: stop; best=49
answer: 49

ছোট input-এ ধাপে ধাপে

Input [1, 2, 1]:

  1. শুরু: left=0 (1), right=2 (1), best=0।
  2. area = min(1,1) * (2-0) = 1 * 2 = 2; best=2। height[0] < height[2]? 1 < 1 মিথ্যা → right কমাও → right=1।
  3. left=0 (1), right=1 (2): area = min(1,2) * 1 = 1; best 2-ই থাকে। 1 < 2 সত্য → left=1।
  4. left < right মিথ্যা (1 < 1 নয়) → loop শেষ। ফল: best = 2।

কোড ও ব্যাখ্যা

Python

Python
def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        h = min(height[left], height[right])
        best = max(best, h * (right - left))
        if height[left] < height[right]:   # ছোট দেয়াল ভেতরে সরাও
            left += 1
        else:
            right -= 1
    return best

# ---- tests ----
assert max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49
assert max_area([1, 1]) == 1
assert max_area([4, 3, 2, 1, 4]) == 16     # দুই প্রান্তের 4
assert max_area([1, 2, 1]) == 2
print("সব test pass!")

কোডের প্রতিটি অংশ

  • left, right = 0, len(height) - 1 — দুই pointer দুই প্রান্তে, width সর্বোচ্চ থেকে শুরু।
  • while left < right — ওরা দেখা করার আগ পর্যন্ত।
  • h = min(height[left], height[right]) — পানির উচ্চতা ছোট দেয়ালেই সীমিত।
  • best = max(best, h * (right - left)) — এখনকার area দিয়ে সেরা update।
  • if height[left] < height[right]: left += 1 else: right -= 1 — ছোট দেয়ালটা ফেলে ভেতরে আসা; সমান হলে যেকোনো একটা সরালেই চলে।

Output মিলিয়ে দেখা

[1,8,6,2,5,4,8,3,7] → L=1,R=8 জোড়ায় min(8,7)*7 = 49, এর পরের কোনো জোড়া আর ছাড়ায় না → 49, assert pass। [1,1] → 1; [4,3,2,1,4] → দুই প্রান্তের 4, 4*4=16; [1,2,1] → 2। শেষে print: সব test pass!।

JavaScript ও test cases

দুই প্রান্তের pointer আর Math.min দিয়ে area — ছোট দেয়াল সরিয়ে ভেতরে আসা।

JavaScript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// max water area between two walls (converging two pointers)
function maxArea(height) {
  let left = 0, right = height.length - 1;
  let best = 0;
  while (left < right) {
    const h = Math.min(height[left], height[right]);
    best = Math.max(best, h * (right - left));
    if (height[left] < height[right]) left++;   // ছোট দেয়াল ভেতরে সরাও
    else right--;
  }
  return best;
}
// ---- test cases (example + edge) ----
assert(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]) === 49, "classic");
assert(maxArea([1, 1]) === 1, "min-two");
assert(maxArea([4, 3, 2, 1, 4]) === 16, "equal-ends");          // edge
assert(maxArea([1, 2, 1]) === 2, "small");
console.log("সব JS test pass!");

JS টীকা: Math.min/Math.max দিয়ে height আর best হিসাব; area = min(walls) * width — গুণ, যোগ নয়। while (left < right)-এ < রাখলে width 0-এর অপ্রয়োজনীয় iteration এড়ানো যায়।

TypeScript ও test cases

TypeScript
function maxArea(height: number[]): number {
  let left = 0, right = height.length - 1;
  let best = 0;
  while (left < right) {
    const h: number = Math.min(height[left], height[right]);
    best = Math.max(best, h * (right - left));
    if (height[left] < height[right]) left++;
    else right--;
  }
  return best;
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]), 49, "classic");
expect(maxArea([4, 3, 2, 1, 4]), 16, "equal-ends");
expect(maxArea([1, 2, 1]), 2, "small");
console.log("সব TS test pass!");

TS টীকা: height: number[] type-এ index access সব number, তাই Math.min-এ ভুল type ঢোকার সুযোগ নেই; return-ও number বলে caller নিশ্চিন্ত।

খরচ ও সাধারণ ভুল

সময়

O(n) — দুই pointer একসাথে মিলিয়ে মোট n step; প্রতিটা step O(1)।

অতিরিক্ত জায়গা

O(1) — শুধু left, right, best — তিনটা scalar।

যে ভুলগুলো এড়াতে হবে

  • বড় দেয়াল সরিয়ে ফেলা — তখন bottleneck (ছোট দেয়াল) থেকেই যায়, আর ভালো জোড়া হারাতে পারো।
  • area-তে height যোগ করা বা width ভুলে যাওয়া — area = min(height) * width, যোগ নয় গুণ।
  • while left <= right লেখা — left == right হলে width 0, অপ্রয়োজনীয় iteration (ক্ষতি নেই, তবে < পরিষ্কার)।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: converging two pointers (Reverse String #1, Two Sum II-এর discard যুক্তি)। chapter-এর ../patterns.md-এর "Pattern 1 — Two Pointers" দেখো; "প্রতিটা move candidate চিরতরে বাদ দেয়" — এটাই এখানে ছোট দেয়াল discard।

পরের অনুশীলন

কৌশলটি মনে রাখুন

Two pointers (discard argument): দুই প্রান্ত থেকে শুরু করে এমন pointer সরাও যেটা কোনো সেরা উত্তর হারায় না। "container / pair of walls / max area" দেখলেই এই ছোট-দেয়াল-discard মনে করো — O(n)।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "area = min(দুই দেয়াল) × width; দুই প্রান্ত থেকে শুরু করে সবসময় ছোট দেয়াল ফেলে ভেতরে আসো।" "max area / best pair of walls" দেখলেই converging two-pointer মনে করবে — O(n) time, O(1) space।

কোথায় কাজে লাগে

  • Resource/capacity planning: দুই সীমানার মধ্যে সর্বোচ্চ ধারণক্ষমতা (bottleneck = ছোট সীমা) বের করা — যেমন দুই pillar-এর মাঝে সর্বোচ্চ load।
  • Two-pointer optimization base: যেকোনো "best pair under a constraint" সমস্যায় O(n²) এড়িয়ে converging pointer ব্যবহার।
  • Image/UI layout: দুই boundary-র মাঝে সবচেয়ে বড় fit-করা rectangle/panel বের করা।
  • Reservoir/tank design: দুই দেয়ালের উচ্চতার ছোটটা দিয়ে সর্বোচ্চ ধারণযোগ্য আয়তন আন্দাজ করা।
  • Trading spreads: দুই price level-এর মধ্যে সর্বোচ্চ সম্ভাব্য area/coverage হিসাব।
  • Networking: দুই node-এর মধ্যে bottleneck bandwidth (min link) দিয়ে throughput estimate।

মূল pattern: bottleneck হলো ছোট প্রান্ত — তাই সেটাই সরাও; "max area / best pair of walls" দেখলেই converging two-pointer।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।