Problem link ও উৎস
- **Original source:** Classic converging two-pointer exercise
- **Platform:** LeetCode —
- **Topic:** array / two pointers
- **Difficulty:** Medium
- **Pattern:** two pointers (দুই প্রান্ত থেকে, ছোট দেয়াল discard)
- **Basic idea inherited from:** pair-sum-এর discard argument — প্রতিটা move-এ একটা candidate চিরতরে বাদ দেওয়া যায় বলে O(n)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array `height` দেওয়া, যেখানে `height[i]` হলো i-তম খাড়া দেয়ালের উচ্চতা (সব দেয়ালের মধ্যে দূরত্ব 1)। দুটো দেয়াল বেছে তাদের মধ্যে পানি ধরলে কত পানি ধরে = `min(দুই দেয়ালের উচ্চতা) * (দুই দেয়ালের মধ্যে দূরত্ব)`। সবচেয়ে বেশি কত পানি (area) ধরা সম্ভব, সেটা বের করো।
```text
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 {#8-example-input-and-output}
```text
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
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো দুজন দুই প্রান্তে দাঁড়িয়ে একটা চাদর ধরে পানি ধরার চেষ্টা করছে। যে কম উঁচুতে ধরে আছে, পানি তো তার উচ্চতাতেই উপচাবে। তাই যে নিচে ধরে আছে সে-ই এক ঘর ভেতরে এসে আরও উঁচু জায়গায় ধরার চেষ্টা করুক — উঁচু জনকে সরালে শুধু চাদরই ছোট হবে, লাভ নেই।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত **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/](../../01-math-based-programming-fundamentals/06-two-pointers-sliding-window-math/README.md)-তে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: area = `min(h[L], h[R]) * (R - L)`। দুই প্রান্ত থেকে শুরুতে width সবচেয়ে বড়। এখন **ছোট দেয়ালটা** সরানোই যুক্তিযুক্ত — কারণ সেই ছোট দেয়াল ধরে রাখলে width তো কমবেই, আর উচ্চতাও ওই ছোট দেয়ালেই আটকে; তাই ছোট দেয়াল ফেলে দিলে কোনো বড় উত্তর হারানোর ভয় নেই। বড় দেয়াল সরালে উল্টো ভালো জোড়া হারাতে পারতাম।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra data structure লাগে না — শুধু **দুটো integer pointer** (`left`, `right`) আর একটা `best`। O(1) extra space।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Array-র O(1) random access-এ `height[left]` আর `height[right]` সাথে সাথে পড়া যায়। দুই প্রান্ত থেকে ভেতরে আসা two-pointer scan-এ প্রতিটা index একবারই ছোঁয়া হয়, তাই সব O(n^2) জোড়া না দেখেও সেরা area পাওয়া যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা জোড়া দেয়াল `(i, j)` ধরে area হিসাব করে সবচেয়ে বড়টা রাখো — দুটো nested loop।
```text
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)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুটো nested loop মানে প্রায় `n*(n-1)/2` জোড়া — **O(n^2)**। array বড় হলে খুব ধীর। অথচ দুই প্রান্ত থেকে শুরু করে প্রতিটা step-এ ছোট দেয়াল ফেলে দিলে এক pass-এই সেরা area পাওয়া যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: দুই প্রান্তের জোড়ায় width সর্বোচ্চ। এখান থেকে ছোট দেয়াল সরালে সম্ভাব্য সেরা উত্তর হারানো যায় না (ছোট দেয়াল ধরে রাখলে height ওতেই সীমিত, width-ও কমবে)। তাই প্রতিটা step একটা দেয়াল চিরতরে বাদ দেয় — n step-এ শেষ।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`left=0`, `right=n-1`। যতক্ষণ `left < right`: এখনকার area (`min(h[left],h[right]) * (right-left)`) দিয়ে `best` update করো, তারপর যে প্রান্তের দেয়াল ছোট সেটা ভেতরে সরাও (সমান হলে যেকোনো একটা)। ওরা দেখা করলেই শেষ। এক pass, O(n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব জোড়া try করব" (O(n^2)) ভুলে গিয়ে ভাবো "দুই প্রান্ত থেকে শুরু করব, সবসময় ছোট দেয়ালটা ফেলে ভেতরে আসব।" ছোট দেয়াল-ই bottleneck, তাই সেটা সরানোই একমাত্র যুক্তিসঙ্গত move।
### ছবিতে বোঝা {#7-visual-explanation}
`height = [1, 8, 6, 2, 5, 4, 8, 3, 7]` দিয়ে দুই pointer:
```text
L=0(1) R=8(7): area = min(1,7)*8 = 8 ; h[L]