Problem link ও উৎস
- **Original source:** LeetCode Container With Most Water
- **Platform:** LeetCode —
- **Topic:** Two pointers → greedy move with correctness proof
- **Difficulty:** Medium
- **Pattern:** move shorter wall (ছোট দেয়াল সরাও — প্রমাণসহ greedy)
- **Basic idea inherited from:** 081 — Two Sum Sorted (দুই প্রান্ত থেকে চাপা, তবে move-এর যুক্তি আলাদা)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`height` নামে একটা array দেওয়া — প্রতিটা সংখ্যা একটা খাড়া দেয়ালের উচ্চতা, পাশাপাশি বসানো (দূরত্ব 1 করে)। যেকোনো **দুটো** দেয়াল বাছলে তারা x-অক্ষের সাথে একটা পাত্র বানায়। সেই পাত্রে কত পানি ধরবে, তার সর্বোচ্চ মান বের করো।
দুটো দেয়ালের মাঝে পানি ধরে = `min(দুই দেয়ালের উচ্চতা) × (মাঝের দূরত্ব)`। ছোট দেয়ালটাই সীমা — পানি তার উপরে উপচে যায়।
### Input ও output {#6-example-input-and-output}
```text
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)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো দুজন মানুষ দুই হাতে একটা লম্বা পর্দা ধরে আছে, একজনের হাত নিচু, একজনের উঁচু। পর্দায় কতটা পানি জমবে তা ঠিক করে **নিচু হাতটাই** — পানি ওই উচ্চতার উপরে গেলেই গড়িয়ে পড়ে।
এখন তুমি একজনকে ভেতরে ডাকবে (দূরত্ব কমবে)। উঁচু হাতওয়ালাকে ডাকলে? নিচু হাতই এখনো সীমা, উচ্চতা বাড়ল না, উল্টো দূরত্ব কমল — নিশ্চিত লস। তাই **নিচু হাতওয়ালাকে** ভেতরে ডাকো — অন্তত উচ্চতা বাড়ার আশা থাকে। এই সহজ যুক্তিই পুরো algorithm।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-এর পরের ধাপ।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **প্রমাণসহ greedy** — প্রতি step-এ এমন একটা সিদ্ধান্ত নেওয়া যেটা যুক্তি দিয়ে দেখানো যায় "এতে কোনো ভালো উত্তর হারাচ্ছি না"। area = `min(h[l], h[r]) × (r − l)`। দুই প্রান্ত থেকে শুরু করে প্রতি step-এ **ছোট দেয়াল** সরাই, কারণ সেটাই width না কমিয়ে উচ্চতা বাড়ানোর একমাত্র সুযোগ।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরল পথ — সব জোড়া দেয়াল ধরে 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
```
ঠিক উত্তর দেয় — প্রতিটা সম্ভাব্য পাত্র দেখে সর্বোচ্চটা রাখে।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সব জোড়া = প্রায় n²/2 পাত্র। n = 100000 হলে প্রায় ৫০০ কোটি — Time Limit Exceeded।
```text
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-তে কোড নয়, এই "কেন ছোটটা" যুক্তিটাই আসল নম্বর — তাই মুখে বলার মতো করে গুছিয়ে রাখো।
### ছবিতে বোঝা {#5-visual-explanation}
দুই দেয়াল আর তাদের মাঝের পানি (`height = [1, 8, 6, 2, 5, 4, 8, 3, 7]`):
```text
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--
```
কেন ছোটটা সরাই — ছবি দিয়ে:
```text
ধরো h[l] < h[r]:
r সরালে → width কমে, উচ্চতা এখনো বড়জোর h[l] → নিশ্চিত ≤ আগের area
l সরালে → width কমে, কিন্তু উচ্চতা h[l]-এর চেয়ে বাড়তে পারে → আশা আছে
তাই ছোট দেয়াল (l) সরাই — বড়টা রেখে কোনো লাভ নেই।
```
### ছোট input-এ ধাপে ধাপে {#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 দিয়ে আর কোনো বড় পাত্র সম্ভব না।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
l, r = 0, len(height) - 1 ; best = 0
```
দুই আঙুল দুই প্রান্তে — সবচেয়ে চওড়া পাত্র দিয়ে শুরু (width সর্বোচ্চ)।
```text
area = min(height[l], height[r]) * (r - l)
if area > best: best = area
```
বর্তমান পাত্রের পানি = ছোট দেয়াল × দূরত্ব; সেরাটা ধরে রাখি।
```text
if height[l] < height[r]: l += 1
else: r -= 1
```
ছোট দেয়াল যেদিকে, সেটা সরাই — কারণ ছোটটা রেখে কোনো ভালো পাত্র আর সম্ভব না (এটাই প্রমাণ)। সমান হলে যেকোনো একটা সরালেই চলে (দুটোই সীমা)।
```text
return best
```
while শেষ (দুজন মিশে গেল) — সর্বোচ্চ area ফেরত।
`max_area_brute` শুধু test যাচাইয়ের reference; random case-এ দুই পথ মিলিয়ে দেখা হয়।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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]` হলে যেকোনো একটা সরালেই চলে; দুটোই সীমা, কোনোটা রেখে লাভ নেই।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode Container With Most Water** (