084 — Container With Most Water¶

এই note-টা interview-র এক প্রিয় "কেন?" প্রশ্ন। দুই প্রান্ত থেকে দুই আঙুল — এ পর্যন্ত চেনা। কিন্তু এখানে move করার নিয়মটা শুধু মুখস্থ করলে চলবে না, প্রমাণ করতে হবে: কেন ছোট দেয়ালটা সরানো নিরাপদ, আর বড়টা সরালে কেন কিছু পাওয়ার নেই। সেই যুক্তিটা নিজের ভাষায় বলতে পারাই এখানকার আসল target। ধীরে পড়ো।

Problem link ও উৎস

Original source: LeetCode Container With Most Water
Platform: LeetCode — https://leetcode.com/problems/container-with-most-water/
Topic: Two pointers → greedy move with correctness proof
Difficulty: Medium
Pattern: move shorter wall (ছোট দেয়াল সরাও — প্রমাণসহ greedy)
Basic idea inherited from: 081 — Two Sum Sorted (দুই প্রান্ত থেকে চাপা, তবে move-এর যুক্তি আলাদা)

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

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

height নামে একটা array দেওয়া — প্রতিটা সংখ্যা একটা খাড়া দেয়ালের উচ্চতা, পাশাপাশি বসানো (দূরত্ব 1 করে)। যেকোনো দুটো দেয়াল বাছলে তারা x-অক্ষের সাথে একটা পাত্র বানায়। সেই পাত্রে কত পানি ধরবে, তার সর্বোচ্চ মান বের করো।

দুটো দেয়ালের মাঝে পানি ধরে = min(দুই দেয়ালের উচ্চতা) × (মাঝের দূরত্ব)। ছোট দেয়ালটাই সীমা — পানি তার উপরে উপচে যায়।

Input ও output¶

উদাহরণ

height                          ->  max area
-------------------------------------------------
[1, 8, 6, 2, 5, 4, 8, 3, 7]     ->  49     (index 1 ও 8: min(8,7)×7)
[1, 1]                          ->  1      (1 × 1)
[4, 3, 2, 1, 4]                 ->  16     (index 0 ও 4: 4×4)
[1, 2, 1]                       ->  2      (index 0 ও 2: 1×2)
[2, 3, 4, 5, 18, 17, 6]         ->  17     (index 4 ও 5: 17×1)
[1, 2, 4, 3]                    ->  4      (index 1 ও 3: 2×2)

Edge case: ঠিক দুটো দেয়াল হলে একটাই পাত্র; একটার কম হলে পাত্রই হয় না (area 0)।

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

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

এখন তুমি একজনকে ভেতরে ডাকবে (দূরত্ব কমবে)। উঁচু হাতওয়ালাকে ডাকলে? নিচু হাতই এখনো সীমা, উচ্চতা বাড়ল না, উল্টো দূরত্ব কমল — নিশ্চিত লস। তাই নিচু হাতওয়ালাকে ভেতরে ডাকো — অন্তত উচ্চতা বাড়ার আশা থাকে। এই সহজ যুক্তিই পুরো algorithm।

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

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

081 — Two Sum Sorted-এর কাঠামো এক — দুই প্রান্ত থেকে দুই pointer ভেতরে আসে, O(n)। কিন্তু move-এর কারণ ভিন্ন:

081-এ array sorted, তাই sum-এর monotonicity থেকে move ঠিক হয়
084-এ height sorted নয়; move ঠিক হয় area হারানোর প্রমাণ থেকে — ছোট দেয়াল রেখে বড়টা সরালে নিশ্চিত লস

তাই 084 শেখায়: two-pointer মানে সবসময় sorted নয় — কখনো move-টা একটা greedy correctness argument থেকে আসে। এই গভীরতাটাই 081-এর পরের ধাপ।

ভেতরের অঙ্ক¶

মূল idea হলো প্রমাণসহ greedy — প্রতি step-এ এমন একটা সিদ্ধান্ত নেওয়া যেটা যুক্তি দিয়ে দেখানো যায় "এতে কোনো ভালো উত্তর হারাচ্ছি না"। area = min(h[l], h[r]) × (r − l)। দুই প্রান্ত থেকে শুরু করে প্রতি step-এ ছোট দেয়াল সরাই, কারণ সেটাই width না কমিয়ে উচ্চতা বাড়ানোর একমাত্র সুযোগ।

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

প্রথম সরল উপায়¶

সরল পথ — সব জোড়া দেয়াল ধরে area মাপা:

Python

def max_area_brute(height):
    n = len(height)
    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)
    return best

ঠিক উত্তর দেয় — প্রতিটা সম্ভাব্য পাত্র দেখে সর্বোচ্চটা রাখে।

কোথায় বেশি কাজ হতে পারে¶

সব জোড়া = প্রায় n²/2 পাত্র। n = 100000 হলে প্রায় ৫০০ কোটি — Time Limit Exceeded।

উদাহরণ

n = 100000 হলে:
  brute force  : ~5,000,000,000 জোড়া      (O(n²))
  two pointers : বড়জোর 100000 step         (O(n))

মূল অপচয়: ছোট দেয়াল রেখে বড়টা সরানো জোড়াগুলো কখনোই ভালো হতে পারে না — তবু brute force সেগুলোও মাপছে।

আরও ভালোভাবে ভাবা¶

মূল insight (প্রমাণসহ): দুই প্রান্ত থেকে শুরু করো; প্রতি step-এ ছোট দেয়ালটা ভেতরে সরাও।

কেন নিরাপদ? ধরো h[l] ≤ h[r]। l-কে অন্য যেকোনো r' < r-এর সাথে জোড়া দিলে: width r' − l < r − l, আর উচ্চতা min(h[l], h[r']) ≤ h[l]। মানে l-এর জড়িত আর কোনো জোড়াই বর্তমানটার চেয়ে বড় হতে পারে না → l-কে চিরতরে বাদ দেওয়া নিরাপদ → l++।

প্রতি step-এ এক দেয়াল চিরতরে বাদ → বড়জোর n step → O(n)।

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

আসল "আহা!": ছোট দেয়াল-ই বর্তমান area-র সীমা; তাকে রেখে দিলে এর সব জোড়া ইতিমধ্যে দেখা সেরাটার চেয়ে খারাপ — তাই নিশ্চিন্তে তাকে বিদায় দাও।

এটা মুখস্থ নিয়ম নয়, একটা প্রমাণ। Interview-তে কোড নয়, এই "কেন ছোটটা" যুক্তিটাই আসল নম্বর — তাই মুখে বলার মতো করে গুছিয়ে রাখো।

ছবিতে বোঝা¶

দুই দেয়াল আর তাদের মাঝের পানি (height = [1, 8, 6, 2, 5, 4, 8, 3, 7]):

উদাহরণ

height index:  0   1   2   3   4   5   6   7   8
height value:  1   8   6   2   5   4   8   3   7

l=0 (h=1), r=8 (h=7):
     |~~~~~~~~~~~~~~~~~~~~~~~~~~|   পানির উচ্চতা = min(1,7) = 1
   1 |####|   |   |   |   |   | | 7   area = 1 × 8 = 8   → ছোট দেয়াল 1, l++

l=1 (h=8), r=8 (h=7):
     |~~~~~~~~~~~~~~~~~~~~~|        পানির উচ্চতা = min(8,7) = 7
   8 |#######|...........| | 7      area = 7 × 7 = 49  → ছোট দেয়াল 7, r--

কেন ছোটটা সরাই — ছবি দিয়ে:

উদাহরণ

ধরো  h[l] < h[r]:
  r সরালে → width কমে, উচ্চতা এখনো বড়জোর h[l]  → নিশ্চিত ≤ আগের area
  l সরালে → width কমে, কিন্তু উচ্চতা h[l]-এর চেয়ে বাড়তে পারে → আশা আছে
তাই ছোট দেয়াল (l) সরাই — বড়টা রেখে কোনো লাভ নেই।

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

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]। l=0, r=8, best=0:

step	l	r	h[l]	h[r]	area = min×(r−l)	best	কে সরল
1	0	8	1	7	1×8 = 8	8	h[l]=1 ছোট → l++
2	1	8	8	7	7×7 = 49	49	h[r]=7 ছোট → r--
3	1	7	8	3	3×6 = 18	49	h[r]=3 ছোট → r--
4	1	6	8	8	8×5 = 40	49	সমান → যেকোনো একটা, ধরো r--
5	1	5	8	4	4×4 = 16	49	h[r]=4 ছোট → r--
...					(বাকিগুলো ≤ 49)	49

উত্তর 49। লক্ষ করো step 1-এ index 0 (উচ্চতা 1)-কে চিরতরে বাদ দিলাম — উচ্চতা 1 দিয়ে আর কোনো বড় পাত্র সম্ভব না।

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

Python¶

Python

def max_area(height):
    """দুটো দেয়ালের মাঝে সর্বোচ্চ পানি (area) ফেরত দেয়।"""
    l, r = 0, len(height) - 1
    best = 0
    while l < r:
        area = min(height[l], height[r]) * (r - l)
        if area > best:
            best = area
        if height[l] < height[r]:
            l += 1            # ছোট দেয়াল বাঁয়ে → l সরাও (আশা আছে)
        else:
            r -= 1            # ছোট দেয়াল ডানে (বা সমান) → r সরাও
    return best


def max_area_brute(height):
    """ধীর reference — সব জোড়া দেয়াল যাচাই।"""
    n = len(height)
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            area = min(height[i], height[j]) * (j - i)
            if area > best:
                best = area
    return best


# --- ছোট test গুলো (সব pass করা উচিত) ---
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
assert max_area([1, 2, 1]) == 2
assert max_area([2, 3, 4, 5, 18, 17, 6]) == 17
assert max_area([1, 2, 4, 3]) == 4
assert max_area([5]) == 0           # একটা দেয়াল → পাত্রই হয় না

# brute force-এর সাথে মিলিয়ে দেখা (নানা random case)
import random
random.seed(13)
for _ in range(400):
    h = [random.randint(0, 9) for _ in range(random.randint(0, 12))]
    assert max_area(h) == max_area_brute(h), h

print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))   # 49
print(max_area([4, 3, 2, 1, 4]))               # 16
print(max_area([1, 1]))                        # 1
print("সব test pass!")

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

উদাহরণ

l, r = 0, len(height) - 1 ; best = 0

দুই আঙুল দুই প্রান্তে — সবচেয়ে চওড়া পাত্র দিয়ে শুরু (width সর্বোচ্চ)।

উদাহরণ

area = min(height[l], height[r]) * (r - l)
if area > best: best = area

বর্তমান পাত্রের পানি = ছোট দেয়াল × দূরত্ব; সেরাটা ধরে রাখি।

উদাহরণ

if height[l] < height[r]: l += 1
else:                     r -= 1

ছোট দেয়াল যেদিকে, সেটা সরাই — কারণ ছোটটা রেখে কোনো ভালো পাত্র আর সম্ভব না (এটাই প্রমাণ)। সমান হলে যেকোনো একটা সরালেই চলে (দুটোই সীমা)।

উদাহরণ

return best

while শেষ (দুজন মিশে গেল) — সর্বোচ্চ area ফেরত।

max_area_brute শুধু test যাচাইয়ের reference; random case-এ দুই পথ মিলিয়ে দেখা হয়।

Output মিলিয়ে দেখা¶

চালালে ছাপবে:

উদাহরণ

49
16
1
সব test pass!

প্রথম লাইন classic example-এর 49; দ্বিতীয় লাইন [4,3,2,1,4]-এর দুই প্রান্তের 4×4 = 16; তৃতীয় লাইন [1,1]-এর 1। তার আগে 400 random case brute-force-এর সাথে মিলেছে, তাই সব test pass!।

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

সময়¶

O(n) — প্রতি step-এ l বাড়ে বা r কমে, মানে window ১ ঘর সংকুচিত; মোট বড়জোর n step। sorting লাগে না — move-এর যুক্তি area-র প্রমাণ থেকে আসে, structure থেকে নয়।

অতিরিক্ত জায়গা¶

O(1) — শুধু l, r, best, area — গুটিকয় variable; বাড়তি কোনো array নেই।

যে ভুলগুলো এড়াতে হবে¶

বড় দেয়াল সরানো — ছোটটা রেখে বড়টা সরালে নিশ্চিত লস; সবসময় ছোট দেয়াল সরাও।
height যোগ করে ফেলা — পানি ঠিক করে min, যোগফল নয়; min(h[l], h[r])।
দূরত্বে +1 বসানো — দূরত্ব r − l (index-এর ফারাক), r − l + 1 নয়।
প্রমাণটা না জানা — interview-তে "কেন ছোটটা" না বলতে পারলে মুখস্থ মনে হয়; যুক্তিটা গুছিয়ে রাখো।
সমান উচ্চতায় আটকে যাওয়া — h[l]==h[r] হলে যেকোনো একটা সরালেই চলে; দুটোই সীমা, কোনোটা রেখে লাভ নেই।

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

এই ধারণার পরের অনুশীলন¶

LeetCode Container With Most Water (https://leetcode.com/problems/container-with-most-water/) — এই problem-এরই মূল রূপ।
LeetCode Trapping Rain Water (https://leetcode.com/problems/trapping-rain-water/) — আরো গভীর two-pointer, প্রতি কলামে আটকানো পানি।
LeetCode 3Sum (https://leetcode.com/problems/3sum/) — একই দুই-প্রান্ত পরিবার, তবে move sorted থেকে (083)।

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

Two pointers with a greedy-move proof — দুই প্রান্ত থেকে শুরু, ছোট দেয়াল সরাও, কারণ তাকে রেখে কোনো ভালো ফল সম্ভব না। বড় শিক্ষা: two-pointer move সবসময় sorting থেকে আসে না — কখনো একটা correctness argument ("এই প্রান্ত রাখলে সব জোড়া খারাপ") থেকেই আসে।

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

ভবিষ্যতের আমাকে এক লাইনে: "পাত্রের পানি = min(দুই দেয়াল) × দূরত্ব; দুই প্রান্ত থেকে শুরু, প্রতি step-এ ছোট দেয়াল সরাও — কারণ তাকে রেখে কোনো জোড়াই ভালো হতে পারে না। Signal: 'দুই দেয়াল/দুই প্রান্ত + max area' দেখলে ছোট-দেয়াল greedy মনে পড়ুক, আর প্রমাণটা মুখে বলতে পারা চাই।"

পরের ধাপ → 085 — Sliding Window Sum (এবার আঙুল ছেড়ে জানালার হাতেখড়ি)। ভিত্তি → 081 — Two Sum Sorted।

ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

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