Problem link ও উৎস
- **Original source:** Classic two-pointer / prefix-max exercise
- **Platform:** LeetCode —
- **Topic:** array / two pointers
- **Difficulty:** Hard
- **Pattern:** two pointers / prefix max (প্রতিটা ঘরের উপর জমা পানি)
- **Basic idea inherited from:** prefix-max array + two-pointer discard — দুই প্রান্তের boundary বুঝে candidate বাদ দেওয়া
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array `height` দেওয়া, যেখানে প্রতিটা সংখ্যা একটা দেয়াল/বারের উচ্চতা (প্রস্থ 1)। বৃষ্টির পর এই বারগুলোর মাঝের গর্তে কতটুকু পানি জমে থাকবে, তার মোট পরিমাণ বের করো।
```text
height = [0,1,0,2,1,0,1,3,2,1,2,1]
জমা পানি (#) মোট = 6 একক
```
### Input ও output {#8-example-input-and-output}
```text
Input : [0,1,0,2,1,0,1,3,2,1,2,1] -> 6
Input : [4,2,0,3,2,5] -> 9
Edge case 1 (খালি/monotonic): [] -> 0 ; [1,2,3] -> 0 (কোনো গর্ত নেই)
Edge case 2 (এক গর্ত): [3,0,2] -> 2
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো দুই পাশে দুজন বালতি হাতে দাঁড়িয়ে, মাঝখানে অসমান উঁচু-নিচু দেয়াল। যে পাশের সবচেয়ে উঁচু দেয়াল **ছোট**, সেই পাশ থেকে এক ঘর ভেতরে এসো — কারণ ওই ঘরে পানি কতটা দাঁড়াবে তা ওই ছোট পাশের উচ্চতাই ঠিক করে দেয়, ওপাশে নিশ্চিত আরও উঁচু দেয়াল আছে। এভাবে ছোট পাশ থেকে এগোতে এগোতে মাঝে মিলে যাও।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত দুটো: (১) **prefix-max thinking** — কোনো ঘরের উপর কতটা পানি জমবে তা নির্ভর করে তার বাঁ দিকের সর্বোচ্চ দেয়াল আর ডান দিকের সর্বোচ্চ দেয়ালের ছোটটার উপর। (২) **two-pointer discard** (problem 12, Container With Most Water-এর জ্ঞাতি) — দুই প্রান্ত থেকে এগিয়ে এসে, যে দিকের boundary ছোট সেই দিকটা নিরাপদে নিষ্পত্তি করা। prefix চিন্তার গভীরে: [../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা সূত্র: index `i`-এর উপর জমা পানি = `min(leftMax_i, rightMax_i) - height[i]` (ঋণাত্মক হলে 0)। এখানে `leftMax_i` = `0..i` পর্যন্ত সর্বোচ্চ, `rightMax_i` = `i..n-1` পর্যন্ত সর্বোচ্চ। মোট পানি = সব `i`-এর এই মানের যোগফল। two-pointer চাল এই সত্যকে কাজে লাগায়: যদি `leftMax < rightMax` হয়, তবে বাঁ দিকের ঘরের ভাগ্য শুধু `leftMax`-ই ঠিক করে দেয় (ডান দিকে এর চেয়ে উঁচু দেয়াল নিশ্চিত আছে), তাই সেই ঘর এখনই হিসাব করে ফেলা নিরাপদ।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুটো সংস্করণ:
- **Prefix-max array (সহজ বোঝা):** দুটো array `leftMax`, `rightMax` (O(n) extra)।
- **Two pointers (optimal):** কোনো extra array নয় — শুধু `left`, `right` pointer আর `left_max`, `right_max` দুটো scalar; **O(1) extra space**।
এখানে optimal দুই-pointer version-টাই দেখাব।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
পানি জমার শর্ত পুরোটাই "বাঁয়ের সর্বোচ্চ বনাম ডানের সর্বোচ্চ" নিয়ে — তাই দুই প্রান্ত থেকে দুটো running max রাখলেই চলে। array-র O(1) random access-এ দুই প্রান্তের উচ্চতা সাথে সাথে পড়া যায়। ছোট-boundary-ওয়ালা দিকটা যেহেতু চূড়ান্ত হয়ে গেছে, সেটা এগিয়ে দিলে প্রতিটা ঘর ঠিক একবার নিষ্পত্তি হয় — extra array ছাড়াই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা ঘর `i`-এর জন্য আলাদা করে তার বাঁ দিকের সর্বোচ্চ আর ডান দিকের সর্বোচ্চ scan করে বের করো, তারপর `min(leftMax, rightMax) - height[i]` যোগ করো।
```text
total = 0
for i in range(n):
leftMax = max(height[0..i]) # বাঁ স্ক্যান
rightMax = max(height[i..n-1]) # ডান স্ক্যান
total += max(0, min(leftMax, rightMax) - height[i])
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা ঘরের জন্য দুই দিকেই আবার scan — **O(n^2)**। একই max বারবার গোনা হচ্ছে। দুটো সমাধান: (ক) আগে থেকে `leftMax`/`rightMax` prefix array বানিয়ে O(n) time কিন্তু O(n) space; (খ) two-pointer দিয়ে O(n) time **এবং** O(1) space — এই শেষেরটাই সেরা।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: কোনো ঘরের পানি কেবল `min(leftMax, rightMax)`-এর উপর নির্ভর করে। দুই প্রান্ত থেকে এগোলে, যে দিকের running max **ছোট**, সেই দিকের বর্তমান ঘরের জন্য `min` নিশ্চিতভাবেই সেই ছোট max — কারণ অন্য প্রান্তে এর চেয়ে বড় কিছু আছে বলেই সে ছোট। তাই ওই ঘর এখনই হিসাব করে ফেলা নিরাপদ, ওপাশ না জেনেও।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`left=0`, `right=n-1`, `left_max=height[left]`, `right_max=height[right]`। যতক্ষণ `left < right`: যদি `left_max < right_max`, তবে `left` এক ঘর ডানে নাও, `left_max` update করো, আর `left_max - height[left]` পানি যোগ করো (সবসময় ≥ 0, কারণ `left_max` update-এর পর `≥ height[left]`)। নইলে ডান দিকে symmetric কাজ করো। মাঝে মিলে গেলে শেষ। এক pass, O(1) extra।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতিটা ঘরের জন্য দুই দিকে max খুঁজব" (O(n^2)) ছাড়ো। ভাবো "যে পাশের সর্বোচ্চ দেয়াল ছোট, সেই পাশের ঘরের পানি ঐ ছোট দেয়ালই ঠিক করে — তাই সেই পাশ এগিয়ে এখনই গুনে ফেলি।" এই discard-যুক্তিই Container With Most Water (#12)-এর সাথে মেলে।
### ছবিতে বোঝা {#7-visual-explanation}
`height = [4,2,0,3,2,5]` — দুই pointer ভেতরে আসছে (ছোট max-এর দিক এগোয়):
```text
L=0(4) R=5(5) leftMax=4 < rightMax=5 -> L এগোও
idx1 h=2: water += 4-2 = 2
idx2 h=0: water += 4-0 = 4 (মোট 6)
idx3 h=3: water += 4-3 = 1 (মোট 7)
idx4 h=2: water += 4-2 = 2 (মোট 9)
idx5: leftMax max(4,5)=5, water += 0 L==R থামো
answer: 9
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[3, 0, 2]`:
1. `left=0(3)`, `right=2(2)`, `left_max=3`, `right_max=2`, `water=0`।
2. `left_max(3) < right_max(2)`? না → ডান শাখা: `right=1`, `right_max=max(2, height[1]=0)=2`, `water += 2-0 = 2`।
3. `left=0`, `right=1`: `left_max(3) < right_max(2)`? না → ডান শাখা: `right=0`, `right_max=max(2, height[0]=3)=3`, `water += 3-3 = 0`।
4. `left=0`, `right=0`: `left < right` মিথ্যা → থামো। ফল: `2`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def trap(height):
if not height:
return 0
left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
water = 0
while left < right:
if left_max < right_max: # বাঁ boundary ছোট -> বাঁ ঘর চূড়ান্ত
left += 1
left_max = max(left_max, height[left])
water += left_max - height[left]
else: # ডান boundary ছোট-সমান -> ডান ঘর চূড়ান্ত
right -= 1
right_max = max(right_max, height[right])
water += right_max - height[right]
return water
# ---- tests ----
assert trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
assert trap([4, 2, 0, 3, 2, 5]) == 9
assert trap([]) == 0 # খালি
assert trap([1, 2, 3]) == 0 # monotonic, কোনো গর্ত নেই
assert trap([3, 0, 2]) == 2 # এক গর্ত
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if not height: return 0` — খালি array-তে পানি নেই।
- `left, right = 0, len(height)-1` — দুই প্রান্তের pointer।
- `left_max, right_max = height[left], height[right]` — দুই পাশের running সর্বোচ্চ।
- `while left < right:` — মাঝে মেলা পর্যন্ত।
- `if left_max < right_max:` — বাঁ পাশের boundary ছোট, তাই বাঁ ঘরের ভাগ্য `left_max`-ই ঠিক করে।
- `left += 1; left_max = max(...); water += left_max - height[left]` — এক ঘর ভেতরে, max হালনাগাদ, জমা পানি যোগ (অঋণাত্মক)।
- `else:` — ডান পাশ ছোট-সমান হলে আয়নায় উল্টো কাজ।
- `return water` — মোট জমা পানি।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[0,1,0,2,1,0,1,3,2,1,2,1]` → দুই pointer এগোতে এগোতে প্রতিটা গর্তের ভাগ যোগ হয়ে `6`, assert pass। `[4,2,0,3,2,5]` → `9`; `[]` → `0`; `[1,2,3]` → ক্রমশ উঁচু, কোনো ঘরে `max - height` ধনাত্মক হয় না → `0`; `[3,0,2]` → মাঝের গর্তে `2`। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
দুই প্রান্তের running max — ছোট-boundary-ওয়ালা পাশ এগিয়ে সেই ঘর তখনই গোনো।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// total trapped rain water (two pointers, O(1) space)
function trap(height) {
if (height.length === 0) return 0;
let left = 0, right = height.length - 1;
let leftMax = height[left], rightMax = height[right];
let water = 0;
while (left < right) {
if (leftMax < rightMax) { // বাঁ boundary ছোট -> বাঁ ঘর চূড়ান্ত
left++;
leftMax = Math.max(leftMax, height[left]);
water += leftMax - height[left];
} else { // ডান boundary ছোট-সমান -> ডান ঘর চূড়ান্ত
right--;
rightMax = Math.max(rightMax, height[right]);
water += rightMax - height[right];
}
}
return water;
}
// ---- test cases (example + edge) ----
assert(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) === 6, "classic");
assert(trap([4, 2, 0, 3, 2, 5]) === 9, "valley");
assert(trap([]) === 0, "empty"); // edge
assert(trap([1, 2, 3]) === 0, "monotonic"); // edge
assert(trap([3, 0, 2]) === 2, "one-pit");
console.log("সব JS test pass!");
```
> **JS টীকা:** `leftMax`/`rightMax` আগে `Math.max`-এ update করে তবেই পানি যোগ করো — তখন মান সবসময় ≥ 0, আলাদা `Math.max(0, …)` লাগে না। ছোট max-এর দিক এগোও; বড় max-এর দিক এগোলে `min` নিশ্চিত নয়, হিসাব ভুল।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function trap(height: number[]): number {
if (height.length === 0) return 0;
let left = 0, right = height.length - 1;
let leftMax: number = height[left], rightMax: number = height[right];
let water = 0;
while (left < right) {
if (leftMax < rightMax) {
left++;
leftMax = Math.max(leftMax, height[left]);
water += leftMax - height[left];
} else {
right--;
rightMax = Math.max(rightMax, height[right]);
water += rightMax - height[right];
}
}
return water;
}
function expect