084 — Container With Most Water¶

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

Source¶

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-এর যুক্তি আলাদা)

1. Problem in simple words¶

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

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

2. What is the math idea?¶

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

3. Which basic idea does this inherit from?¶

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-এর পরের ধাপ।

4. Real-life analogy¶

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

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

5. Visual explanation¶

দুই দেয়াল আর তাদের মাঝের পানি (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) সরাই — বড়টা রেখে কোনো লাভ নেই।

6. Example input and 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)।

7. Brute force thinking¶

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

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

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

8. Why brute force may be slow¶

সব জোড়া = প্রায় 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 সেগুলোও মাপছে।

9. Better thinking¶

মূল 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)।

10. Thinking tweak¶

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

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

11. Step-by-step dry run¶

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 দিয়ে আর কোনো বড় পাত্র সম্ভব না।

12. Python solution¶

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!")

13. Line-by-line explanation¶

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-এ দুই পথ মিলিয়ে দেখা হয়।

14. Output walkthrough¶

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

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!।

15. Time complexity¶

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

16. Space complexity¶

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

17. Common mistakes¶

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

18. Harder problems that inherit this idea¶

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)।

19. Pattern learned¶

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

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "পাত্রের পানি = 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" লেখো।