Problem link ও উৎস
- **Original source:** Classic capstone interview problem (elevation map water trapping)
- **Platform:** LeetCode —
- **Topic:** arrays + stacks + prefix-max
- **Difficulty:** Hard
- **Pattern:** monotonic stack AND two pointers (দুটোই করো)
- **Basic idea inherited from:** এটা একটা cross-topic capstone — এখানে মেশে **02 arrays** (bar-গুলোর height array scan), **stacks** (04 stack and queue-এর monotonic stack), আর **01 math**-এর prefix-max idea (বাঁ ও ডানের সর্বোচ্চ wall)। তিন tool তিন রকম সমাধান দেয়, উত্তর এক।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা non-negative integer array দেওয়া আছে, যেখানে প্রতিটা সংখ্যা একটা bar-এর উচ্চতা (width 1 ধরা)। বৃষ্টি হলে এই উঁচু-নিচু ভূদৃশ্যের গর্তগুলোতে জল জমে। মোট কত একক জল আটকে থাকবে, সেটা বের করো।
প্রতিটা position-এ জমা জল = বাঁ দিকের সর্বোচ্চ wall আর ডান দিকের সর্বোচ্চ wall — এই দুটোর মধ্যে ছোটটা, বিয়োগ ওই position-এর নিজের উচ্চতা (যদি positive হয়)।
```text
heights : [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] -> Output: 6
Input : [4,2,0,3,2,5] -> Output: 9
Edge case 1 (একঘেয়ে বাড়ছে): [1,2,3,4] -> 0 (কোনো গর্ত নেই)
Edge case 2 (খুব ছোট): [2,0,2] -> 2
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একসারি বিভিন্ন উচ্চতার দেয়াল দিয়ে বানানো খুপরি, আর তুমি ওপর থেকে জল ঢালছ। যেকোনো খুপরিতে জল ততটাই জমবে যতটা তার **নিচু পাশের দেয়াল** ধরে রাখতে পারে — উঁচু পাশ যতই উঁচু হোক, জল নিচু পাশ দিয়ে গড়িয়ে পড়বে।
তাই প্রতিটা জায়গায় প্রশ্ন একটাই: "আমার দুই পাশের সবচেয়ে উঁচু দেয়াল দুটোর মধ্যে ছোটটা কত উঁচু?" — সেটাই জলের ছাদ।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এই problem তিনটা আগের ধারণা জোড়া দেয়:
- **02 arrays** থেকে: height array-র উপর index-ধরে scan, আর কোন bar কোথায় বসে সেই thinking।
- **stacks (04 stack and queue)** থেকে: একটা **monotonic (decreasing) stack** — index জমিয়ে রেখে যখন উঁচু bar আসে তখন গর্ত "settle" করা।
- **01 math**-এর prefix-max idea থেকে: প্রতিটা position-এর বাঁ-সর্বোচ্চ আর ডান-সর্বোচ্চ wall একটা running maximum (prefix/suffix max)।
একা array দেয় scan; stack দেয় "কখন একটা গর্ত বন্ধ হলো" ধরা; prefix-max দেয় boundary wall। তিনটে মিলে O(n)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **bounded-by-the-shorter-wall** নিয়ম: position `i`-তে জল জমে `min(leftMax[i], rightMax[i]) - height[i]` (negative হলে 0)। জল কখনো তার নিচু পাশের wall ছাড়িয়ে উঠতে পারে না — তাই ছোট wall-টাই ছাদ ঠিক করে।
পুরো array-র উত্তর = প্রতিটা position-এর এই contribution-এর যোগফল।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
তিন পথ, একই উত্তর:
- **Prefix-max (01) path:** দুটো array — `leftMax`, `rightMax` — অথবা two pointers দিয়ে O(1) space-এ একই হিসাব।
- **Monotonic stack (04) path:** একটা **stack** যেখানে decreasing height-এর index জমা; উঁচু bar এলে layer-by-layer জল যোগ।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Brute force প্রতি position-এ আবার বাঁ ও ডান scan করে — অপচয়, কারণ leftMax/rightMax একবার scan করেই জানা যায় (prefix-max, 01)। two pointers সেই দুই running max-কে O(1) space-এ মিশিয়ে দেয়।
Monotonic stack আরেকটা দৃষ্টিভঙ্গি দেয় (04 stack and queue): এটা "একটা গর্ত কখন বন্ধ হয়" সেই ঘটনা ধরে — যা daily-temperatures-এর মতো "পরের বড় element" pattern-এরই আত্মীয়, তাই দুটো একসাথে শেখা mutually reinforcing।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা position `i`-র জন্য বাঁ দিকের সর্বোচ্চ আর ডান দিকের সর্বোচ্চ আলাদা করে scan করে বের করো, তারপর `min(...) - height[i]` যোগ করো।
```text
for i in range(n):
lm = max(height[0..i])
rm = max(height[i..n-1])
water += max(0, min(lm, rm) - height[i])
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা position-এ বাঁ ও ডান দুটোই পুরো scan — position-প্রতি O(n), মোট **O(n²)**। বড় array-তে ধীর। কারণ একই leftMax/rightMax আমরা বারবার নতুন করে হিসাব করছি — prefix-max (01) precompute সেটা দূর করে, two pointers আবার space-ও O(1)-এ নামায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **জলের ছাদ ঠিক করে নিচু পাশের wall**, আর leftMax/rightMax দুটোই *monotonic* (বাঁ থেকে ডান leftMax কখনো কমে না; ডান থেকে বাঁ rightMax কখনো কমে না)। তাই দুই প্রান্ত থেকে এগোতে এগোতে যে পাশের running max ছোট, সেই পাশের জল নিশ্চিতভাবে settle করা যায় — অন্য পাশ না জেনেও।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**Two-pointer (prefix-max, O(1) space):** `l`, `r` দুই প্রান্তে; `leftMax`, `rightMax` ধরো। যে পাশের height ছোট, সেই pointer এগোও, কারণ ওই পাশের জল ছোট-max দিয়েই bounded — `water += max(0, sideMax - height[ptr])`।
**Monotonic stack (04):** decreasing index জমাও; নতুন bar আগের bar-এর চেয়ে উঁচু হলে, stack থেকে নিচু bar pop করে তার উপরের জল layer যোগ করো (bounded width × bounded height)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতিটা position-এ দুপাশ scan করব" ভাবার বদলে ভাবো "দুই পাশের running max-ই যথেষ্ট, আর যে পাশ ছোট সেই পাশ এখনই settle করা নিরাপদ।" O(n²) double-scan একটা O(n) two-pointer sweep-এ গুটিয়ে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`height=[0,1,0,2,1,0,1,3,2,1,2,1]`। `#` দেয়াল, `~` জল, `.` খালি। প্রতিটি column-এর index নিচে দেওয়া।
```text
level 3 | . . . . . . . # . . . .
level 2 | . . . # ~ ~ ~ # # ~ # .
level 1 | . # ~ # # ~ # # # # # #
+------------------------
index | 0 1 2 3 4 5 6 7 8 9 10 11
```
| Index | Height | বাঁয়ের maximum (নিজেসহ) | ডানের maximum (নিজেসহ) | জমা জল |
| --- | --- | --- | --- | --- |
| 0 | 0 | 0 | 3 | 0 |
| 1 | 1 | 1 | 3 | 0 |
| 2 | 0 | 1 | 3 | 1 |
| 3 | 2 | 2 | 3 | 0 |
| 4 | 1 | 2 | 3 | 1 |
| 5 | 0 | 2 | 3 | 2 |
| 6 | 1 | 2 | 3 | 1 |
| 7 | 3 | 3 | 3 | 0 |
| 8 | 2 | 3 | 2 | 0 |
| 9 | 1 | 3 | 2 | 1 |
| 10 | 2 | 3 | 2 | 0 |
| 11 | 1 | 3 | 1 | 0 |
প্রতিটি cell-এর জল `min(leftMax,rightMax)-height`। মোট `1+1+2+1+1=6`।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Two pointers on `[2,0,2]`:
1. `l=0 (h=2)`, `r=2 (h=2)`, `leftMax=0`, `rightMax=0`, water=0।
2. `height[l]=2 <= height[r]=2` → বাঁ দিক। `leftMax = max(0,2)=2`; water += `2-2 = 0`; `l=1`।
3. `height[l]=0 <= height[r]=2` → বাঁ দিক। `leftMax = max(2,0)=2`; water += `2-0 = 2`; `l=2`।
4. `l == r` → থামো। মোট water = **2**। ✓
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def trap_two_pointer(height):
"""PREFIX-MAX idea (01) + two pointers (02): O(n) time, O(1) space।
যে পাশের height ছোট, সেই পাশের জল ছোট-max দিয়েই bounded — তাই settle নিরাপদ।"""
if not height:
return 0
l, r = 0, len(height) - 1
left_max, right_max = 0, 0
water = 0
while l < r:
if height[l] <= height[r]: # বাঁ পাশ ছোট/সমান -> বাঁ settle
left_max = max(left_max, height[l])
water += left_max - height[l] # bounded by left_max
l += 1
else: # ডান পাশ ছোট -> ডান settle
right_max = max(right_max, height[r])
water += right_max - height[r] # bounded by right_max
r -= 1
return water
def trap_monotonic_stack(height):
"""MONOTONIC STACK (04 stack and queue): decreasing index জমাই; উঁচু bar এলে
নিচু bar pop করে তার উপরের জল layer যোগ করি (width × bounded height)।"""
stack = [] # decreasing height-এর index
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = stack.pop() # জলের তলা
if not stack:
break # বাঁ দেয়াল নেই -> জল ধরবে না
left = stack[-1]
width = i - left - 1 # দুই দেয়ালের মাঝের ফাঁক
bounded = min(height[left], h) - height[bottom]
water += width * bounded
stack.append(i)
return water
def trap_prefix_arrays(height):
"""obviously-correct reference: leftMax আর rightMax array আলাদা করে বানিয়ে যোগ।"""
n = len(height)
if n == 0:
return 0
left_max = [0] * n
right_max = [0] * n
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i - 1], height[i])
right_max[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
right_max[i] = max(right_max[i + 1], height[i])
return sum(min(left_max[i], right_max[i]) - height[i] for i in range(n))
# ---- tests ----
ex1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
assert trap_two_pointer(ex1) == 6
assert trap_monotonic_stack(ex1) == 6
assert trap_prefix_arrays(ex1) == 6
ex2 = [4, 2, 0, 3, 2, 5]
assert trap_two_pointer(ex2) == 9
assert trap_monotonic_stack(ex2) == 9
# edge cases
assert trap_two_pointer([]) == 0 # খালি
assert trap_two_pointer([5]) == 0 # একটা bar
assert trap_two_pointer([1, 2, 3, 4]) == 0 # একঘেয়ে বাড়ছে
assert trap_two_pointer([4, 3, 2, 1]) == 0 # একঘেয়ে কমছে
assert trap_two_pointer([2, 0, 2]) == 2 # ছোট গর্ত
assert trap_monotonic_stack([2, 0, 2]) == 2
# তিন method সবসময় একমত: random fuzz
import random
random.seed(25)
for _ in range(500):
n = random.randint(0, 15)
h = [random.randint(0, 8) for _ in range(n)]
a = trap_two_pointer(h)
b = trap_monotonic_stack(h)
c = trap_prefix_arrays(h)
assert a == b == c, (h, a, b, c)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `trap_two_pointer` — `l`, `r` দুই প্রান্তে; ছোট-height পাশের running max দিয়ে জল bounded, তাই সেই pointer এগিয়ে settle (prefix-max + two pointers)।
- `trap_monotonic_stack` — decreasing index stack; উঁচু bar এলে নিচু bar pop করে `width × (min(দুই দেয়াল) - তলা)` জল যোগ; বাঁ দেয়াল না থাকলে break।
- `trap_prefix_arrays` — `leftMax`/`rightMax` array আলাদা precompute করে position-প্রতি `min - height` যোগ; obviously-correct reference।
- random fuzz তিন method-কে 500 case-এ মিলিয়ে দেখে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[0,1,0,2,1,0,1,3,2,1,2,1]`-এ তিন method-ই 6 দেয়; `[4,2,0,3,2,5]`-এ 9। একঘেয়ে বাড়া/কমা array-তে 0 (গর্ত নেই), `[2,0,2]`-তে 2। শেষে 500 random fuzz-এ two-pointer, monotonic stack, আর prefix-array তিনটাই একমত — তিন দৃষ্টিভঙ্গি, এক উত্তর। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
তিন method-ই **O(n)** — two-pointer একবার sweep, monotonic stack প্রতি index একবার push + একবার pop, prefix-array দুটো scan + একটা যোগ।
### অতিরিক্ত জায়গা {#19-space-complexity}
- two-pointer: **O(1)** (শুধু কয়েকটা variable) — সবচেয়ে ভালো।
- monotonic stack: **O(n)** (worst case সব index stack-এ)।
- prefix-array: **O(n)** (দুটো max array)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `min(leftMax, rightMax)`-এর বদলে শুধু এক পাশের max ব্যবহার করা — জল নিচু পাশ দিয়ে গড়িয়ে পড়ে, তাই ছোটটাই ছাদ।
- two-pointer-এ ভুল পাশ এগোনো — সবসময় *ছোট-height* পাশ এগোতে হবে, তবেই সেই পাশ settle নিরাপদ।
- monotonic stack-এ pop-এর পর stack খালি হলে জল যোগ করা — বাঁ দেয়াল ছাড়া জল ধরে না।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: array single-pass scan (02 arrays, [../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md)) + monotonic stack (04 stack and queue, "পরের বড় element" pattern, এই tracker-এর #14 Daily Temperatures) + prefix/suffix max (01 math, [../../01-math-based-programming-fundamentals/](../../01-math-based-programming-fundamentals/README.md))। তিনটা cold-এ জানা থাকলে তিন সমাধানই নিজে থেকে আসে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Trapping Rain Water II (2D grid, heap + BFS) —