Problem link ও উৎস
- **Original source:** Classic monotonic-stack variant exercise
- **Platform:** LeetCode —
- **Topic:** stack (monotonic variant)
- **Difficulty:** Hard
- **Pattern:** monotonic stack variant (bounded by neighbors)
- **Basic idea inherited from:** Problem 20-এর geometry + "প্রতিবেশী দিয়ে আবদ্ধ" idea — পানি জমে দুই পাশের দেয়ালের নিচু-টার সমান উচ্চতায়
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে কিছু বারের উচ্চতার একটা array `height` দেওয়া আছে (প্রতিটার প্রস্থ 1), যেটা একটা উঁচু-নিচু ভূমিরূপের মতো। বৃষ্টি হলে বারগুলোর মাঝের গর্তে কতটা পানি আটকে থাকবে, তার মোট পরিমাণ বের করো।
`height = [0,1,0,2,1,0,1,3,2,1,2,1]`-এর জন্য আটকে থাকা পানি `6`:
```text
#
#~~~~~~~# #
#~~~# #~~# # # #
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
Input : [2,0,2] -> 2 (মাঝের গর্তে min(2,2)-0 = 2)
Edge case 1 (শুধু বাড়ছে) : [1,2,3] -> 0 (পানি ধরে রাখার দেয়াল নেই)
Edge case 2 (শুধু কমছে) : [3,2,1] -> 0
Edge case 3 (খালি) : [] -> 0
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি বাঁ থেকে ডানে হাঁটছ আর সিঁড়ির মতো নামতে-থাকা ধাপ দেখছ — প্রতিটা ধাপ stack-এ জমছে (decreasing)। হঠাৎ সামনে একটা উঁচু দেয়াল পেলে বুঝলে, পেছনের নামতে-থাকা ধাপগুলোর আর এই দেয়ালের মাঝে একটা "বালতি" তৈরি হয়েছে। তুমি তখন স্তরে স্তরে পানি ঢালো: সবচেয়ে নিচের ধাপ থেকে শুরু করে, যতক্ষণ না বাঁ পাশের দেয়াল বা ডান পাশের দেয়াল বাধা দেয়। প্রতিটা স্তরের পানি মেপে যোগ করতে থাকো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **Problem 20 (largest rectangle)**-এর geometry-চিন্তার জ্ঞাতি, কিন্তু উল্টো প্রশ্ন নিয়ে। সেখানে বারগুলো *নিজেই* আয়তক্ষেত্র ছিল; এখানে আমরা বারের *ফাঁকা জায়গায়* জমা পানির হিসাব করি। মূল ভাবনা — **bounded by neighbors**: যেকোনো জায়গায় পানির উচ্চতা ঠিক হয় বাঁ আর ডান দিকের সবচেয়ে উঁচু দেয়ালের মধ্যে যেটা **ছোট**, তার সমান। monotonic stack এই "বাঁ দেয়াল – গর্ত – ডান দেয়াল" তিনটে এক pass-এ মিলিয়ে দেয়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: একটা নিচু bar-এর উপরে পানি জমবে ঠিক ততটুকু, যতটা তাকে বাঁয়ে আর ডানে ঘিরে রাখা দুই দেয়ালের **নিচু-টা** অনুমতি দেয়, বিয়োগ ওই bar-এর নিজের উচ্চতা।
stack দিয়ে আমরা এই হিসাব **স্তরে স্তরে (layer by layer)** করি। stack-এ উচ্চতা decreasing রাখি। যখন একটা নতুন bar আসে যেটা top-এর চেয়ে উঁচু, তখন top (`bottom`) হলো গর্তের তলা; pop করি, এর নিচের bar (`left`) হলো বাঁ দেয়াল, আর নতুন bar (`right` সীমা) হলো ডান দেয়াল। ওই layer-এ পানি = `(min(left_height, right_height) - bottom_height) * width`।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **monotonic stack** (Python-এ `list`) যেখানে **index** রাখি, উচ্চতা decreasing। index লাগে দুটো কারণে: প্রস্থ (`width`) বের করতে, আর বাঁ-দেয়ালের উচ্চতা `height[left]` দেখতে। আলাদা কিছু লাগে না।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
পানির হিসাবের জন্য প্রতিটা গর্তের দরকার তার বাঁ দিকের নিকটতম উঁচু দেয়াল আর ডান দিকের নিকটতম উঁচু দেয়াল। decreasing stack ঠিক এই "এখনো ডান দেয়াল খুঁজছে" এমন bar-দের ধরে রাখে; একটা উঁচু bar এলে সে stack-এর উপরের নিচু bar-দের ডান দেয়াল হয়ে যায়, আর তাদের নিচের bar বাঁ দেয়াল। প্রতিটা bar একবার push একবার pop → O(n)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: প্রতিটা index `i`-র জন্য তার বাঁ দিকের সর্বোচ্চ উচ্চতা আর ডান দিকের সর্বোচ্চ উচ্চতা বের করি; ওই ঘরে পানি = `min(left_max, right_max) - height[i]` (ঋণাত্মক হলে 0)।
```text
for i in range(n):
left_max = max(height[0 .. i])
right_max = max(height[i .. n-1])
water += max(0, min(left_max, right_max) - height[i])
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা `i`-র জন্য বাঁ ও ডানে আবার scan করলে **O(n^2)**। (precomputed left/right-max array দিয়ে O(n) করা যায়, কিন্তু সেটা অন্য কৌশল।) এখানে আমরা stack দিয়ে এক pass-এ, প্রতিটা bar-কে একবার ছুঁয়ে O(n)-তে পুরো হিসাব সারি — কোনো বাড়তি দুই array না বানিয়েও।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: পানি জমে সবসময় একটা "নিচু জায়গা যাকে দুই পাশে উঁচু দেয়াল ঘিরে রেখেছে" — সেখানে। আর "ডান দিকের নিকটতম উঁচু দেয়াল কখন এল" সেটা ধরা monotonic stack-এর কাজ: যেই একটা উঁচু bar আসে, সে stack-এর উপরের নিচু bar-দের ডান দেয়াল হয়ে যায়, তখনই সেই layer-এর পানি হিসাব করা যায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
index-এর decreasing stack রাখো। প্রতিটা `(i, h)`-তে: যতক্ষণ stack খালি নয় আর top-এর উচ্চতা `h`-এর চেয়ে **ছোট**, ততক্ষণ — `bottom = stack.pop()` (গর্তের তলা)। এরপর stack খালি হলে বাঁ দিকে কোনো দেয়াল নেই, `break`। নাহলে `left = stack[-1]`, প্রস্থ `width = i - left - 1`, আবদ্ধ উচ্চতা `bounded = min(height[left], h) - height[bottom]`, পানি `water += width * bounded`। শেষে `i` push করো।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** পানিকে "প্রতি কলামে কতটা" ভাবার বদলে ভাবো "প্রতিটা অনুভূমিক স্তর কখন বন্ধ হয়"। একটা উঁচু bar এসে পেছনের গর্তের উপরে একটা একটা স্তর ছাদ দিয়ে দেয় — তখনই সেই স্তরের পানি (প্রস্থ × আবদ্ধ-উচ্চতা) যোগ হয়ে যায়। stack ঠিক এই "কোন গর্ত এখনো ডান দেয়ালের অপেক্ষায়" তা মনে রাখে।
### ছবিতে বোঝা {#7-visual-explanation}
`height=[0,1,0,2,1,0,1,3,2,1,2,1]`। Stack-এ index থাকে; top ডানে। প্রতিটি pop-এর layer নিচে দেখানো।
| i / height | pop ও পানির হিসাব | push-এর পরে stack | মোট পানি |
| --- | --- | --- | --- |
| 0 / 0 | pop নেই | `[0]` | 0 |
| 1 / 1 | pop 0: বাঁ দেয়াল নেই | `[1]` | 0 |
| 2 / 0 | pop নেই | `[1, 2]` | 0 |
| 3 / 2 | pop 2: width 1 × layer 1 = 1; pop 1: বাঁ দেয়াল নেই | `[3]` | 1 |
| 4 / 1 | pop নেই | `[3, 4]` | 1 |
| 5 / 0 | pop নেই | `[3, 4, 5]` | 1 |
| 6 / 1 | pop 5: width 1 × layer 1 = 1 | `[3, 4, 6]` | 2 |
| 7 / 3 | pop 6: width 2 × layer 0 = 0; pop 4: width 3 × layer 1 = 3; pop 3: বাঁ দেয়াল নেই | `[7]` | 5 |
| 8 / 2 | pop নেই | `[7, 8]` | 5 |
| 9 / 1 | pop নেই | `[7, 8, 9]` | 5 |
| 10 / 2 | pop 9: width 1 × layer 1 = 1 | `[7, 8, 10]` | 6 |
| 11 / 1 | pop নেই | `[7, 8, 10, 11]` | 6 |
`width=i-left-1`; `layer=min(height[left],height[i])-height[bottom]`। শেষ stack-এর অবশিষ্ট bar-এর জন্য আর ডান দেয়াল নেই; কোনো অতিরিক্ত পানি যোগ হয় না। উত্তর 6।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[2, 0, 2]`:
1. `i=0 (2)`: push → `[0]`
2. `i=1 (0)`: `height[0]=2 < 0`? না; push 1 → `[0,1]`
3. `i=2 (2)`: `height[1]=0 < 2` → `bottom=1` pop; stack `[0]` খালি নয়, `left=0`, `width=2-0-1=1`, `bounded=min(height[0]=2, 2)-height[1]=0 = 2`, `water += 1*2 = 2`; এরপর `height[0]=2 < 2`? না; push 2 → `[0,2]`
4. return `water = 2`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def trap(height):
stack = [] # index রাখে; উচ্চতা decreasing
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 # এই layer-এর পানি
stack.append(i)
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([2, 0, 2]) == 2 # একটা গর্ত
assert trap([1, 2, 3]) == 0 # শুধু বাড়ছে -> পানি ধরে না
assert trap([3, 2, 1]) == 0 # শুধু কমছে
assert trap([]) == 0 # খালি
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `stack = []` — index জমবে; উচ্চতা decreasing রাখা invariant।
- `while stack and height[stack[-1]] < h:` — top-এর bar current-এর চেয়ে নিচু মানে current bar তার ডান দেয়াল হতে পারে, একটা layer বন্ধ হতে চলেছে।
- `bottom = stack.pop()` — pop-করা bar-ই এই layer-এর তলা।
- `if not stack: break` — pop-এর পর stack খালি মানে বাঁ দিকে কোনো দেয়াল নেই; দেয়াল ছাড়া পানি ধরে না, তাই এই `i`-র loop থামাও।
- `left = stack[-1]` / `width = i - left - 1` — বাঁ দেয়াল আর তার-current-এর মাঝের ফাঁকা প্রস্থ।
- `bounded = min(height[left], h) - height[bottom]` — দুই দেয়ালের নিচু-টা পানির ছাদ ঠিক করে; তলা বাদ দিলে এই layer-এর উচ্চতা।
- `water += width * bounded` — এই layer-এর আয়তন যোগ।
- `stack.append(i)` — current bar এখন stack-এ, ভবিষ্যতের দেয়াল/তলা হিসেবে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`trap([0,1,0,2,1,0,1,3,2,1,2,1])` → বিভিন্ন layer যোগ হয়ে মোট `6`; বিশেষ করে index 7-এর `3` এসে পেছনের কয়েকটা bar-এর উপর বড় layer বন্ধ করে। `trap([1,2,3])` → প্রতিবার pop-এর পরই stack খালি হয়ে `break`, কোনো পানি যোগ হয় না, ফল `0`। সব assert pass করে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — প্রতিটা index ঠিক একবার push হয় আর বড়জোর একবার pop হয়; nested `while` সত্ত্বেও মোট pop সংখ্যা n-এর বেশি নয়।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — সবচেয়ে খারাপ ক্ষেত্রে (কঠোর কমতে-থাকা উচ্চতা, যেমন `[5,4,3,2,1]`) কোনো pop হয় না, সব index stack-এ জমে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- pop-এর পর `if not stack: break` ভুলে যাওয়া — বাঁ দেয়াল না থাকলেও পানি যোগ করার চেষ্টায় ভুল উত্তর/error।
- `bounded` হিসাবে `min(height[left], h)` না নিয়ে শুধু একটা দেয়াল ধরা — পানি দুই দেয়ালের নিচু-টা দিয়ে আবদ্ধ, একটা দিয়ে নয়।
- প্রস্থ `i - left - 1`-এর বদলে `i - left` লেখা — দেয়াল দুটো নিজে পানির অংশ নয়, তাই `-1`।
- `<` বনাম `<=` — সমান উচ্চতার ক্ষেত্রে `<` রাখলে সমান bar আগে stack-এ জমে, পরে ঠিকঠাক layer হিসাব হয়; `<=` দিলে অকারণে আগেই pop হয়ে বাঁ-দেয়ালের তথ্য নষ্ট হতে পারে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Problem 20-এর monotonic-stack geometry + "bounded by neighbors" ধারণা; chapter-এর [../patterns.md](../patterns.md) Pattern 4-এর variant। নতুন অংশ — pop-এর মুহূর্তে তিনটে bar (বাঁ দেয়াল, তলা, ডান দেয়াল) মিলিয়ে layer-wise আয়তন।
### পরের অনুশীলন {#22-similar-harder-problems}
- Trapping Rain Water II (2D grid, heap-ভিত্তিক) —