Problem link ও উৎস
- **Original source:** Classic monotonic-stack exercise
- **Platform:** LeetCode —
- **Topic:** stack (monotonic)
- **Difficulty:** Hard
- **Pattern:** monotonic stack
- **Basic idea inherited from:** Problem 9-এর previous/next-smaller machinery — প্রতিটা bar কতদূর বাঁয়ে আর ডানে নিজের উচ্চতা ধরে ছড়াতে পারে
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা histogram দেওয়া আছে — পরপর কিছু বার, প্রতিটার প্রস্থ 1 আর উচ্চতা `heights[i]`। এই বারগুলোর ভেতরে আঁকা যায় এমন **সবচেয়ে বড় আয়তক্ষেত্রের ক্ষেত্রফল** বের করো। আয়তক্ষেত্রটা পরপর কয়েকটা বার জুড়ে থাকতে পারে, কিন্তু তার উচ্চতা ওই অংশের **সবচেয়ে খাটো** বারের সমান।
`heights = [2, 1, 5, 6, 2, 3]`-এর জন্য:
```text
#
# #
# #
# # #
# # # #
# # # # # #
2 1 5 6 2 3
সবচেয়ে বড়: index 2..3 (উচ্চতা min(5,6)=5, প্রস্থ 2) -> 5*2 = 10
```
### Input ও output {#8-example-input-and-output}
```text
Input : [2, 1, 5, 6, 2, 3] -> 10
Input : [2, 4] -> 4 (4*1, বা 2*2 — দুটোই 4)
Input : [6, 2, 5, 4, 5, 1, 6] -> 12 (5,4,5: উচ্চতা 4, প্রস্থ 3)
Edge case 1 (একটা bar) : [5] -> 5
Edge case 2 (একই উচ্চতা) : [3, 3, 3] -> 9 (পুরোটা: 3*3)
Edge case 3 (খালি) : [] -> 0
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো কিছু লোক উচ্চতার ক্রমে (খাটো থেকে লম্বা) একটা সিঁড়িতে দাঁড়িয়ে অপেক্ষা করছে — যতক্ষণ পরের জন আরও লম্বা, সবাই আশায় থাকে "আমার দল আরও ডানে বাড়বে"। হঠাৎ একজন খাটো লোক এসে দাঁড়ালে, তার চেয়ে লম্বা যারা ছিল তাদের সবার "ডান দিকের গল্প শেষ" — প্রত্যেকে তখন হিসাব করে নেয়, সে নিজের উচ্চতা ধরে বাঁ-সীমা থেকে এই খাটো লোক পর্যন্ত কত চওড়া এলাকা ঢাকতে পারত। সেই এলাকাগুলোর সবচেয়ে বড়টাই উত্তর।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **Problem 9 (monotonic stack)**-এর geometry রূপ। সেখানে প্রতিটা element-এর জন্য "next greater" খুঁজছিলে; এখানে প্রতিটা bar-এর জন্য খুঁজি **previous-smaller** আর **next-smaller** — কারণ একটা bar-কে উচ্চতা ধরে রেখে আয়তক্ষেত্র যতদূর বাঁয়ে আর ডানে টানা যায়, সেটা থামে ঠিক যেখানে তার চেয়ে খাটো বার পড়ে। সেই বাঁ-সীমা আর ডান-সীমার মধ্যেকার প্রস্থ × bar-এর উচ্চতা = সেই bar-কে নিচু-সীমা ধরে বানানো সবচেয়ে চওড়া আয়তক্ষেত্র।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: **প্রতিটা সম্ভাব্য আয়তক্ষেত্রের উচ্চতা কোনো-না-কোনো একটা বারের সমান** (যে বারটা ওই আয়তক্ষেত্রের সবচেয়ে খাটো)। তাই প্রতিটা bar `i`-কে "আমিই সবচেয়ে খাটো" ধরে জিজ্ঞেস করি — আমি বাঁয়ে কতদূর আর ডানে কতদূর `heights[i]` উচ্চতা ধরে ছড়াতে পারি?
বাঁয়ে থামি প্রথম `heights[i]`-এর চেয়ে খাটো বারে (previous-smaller), ডানেও তাই (next-smaller)। সেই দুই সীমার মধ্যে প্রস্থ `width`, আর ক্ষেত্রফল `heights[i] * width`। সব bar-এর জন্য এই ক্ষেত্রফলের সর্বোচ্চটাই উত্তর। monotonic stack এই previous/next-smaller এক pass-এই দেয় — pop করার মুহূর্তেই দুই সীমা জানা হয়ে যায়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **monotonic stack** (Python-এ `list`) যেখানে **index** রাখি, আর stack-এ উচ্চতা গুলো নিচ-থেকে-উপর **বাড়তে থাকে** (increasing)। একটা bar যখন pop হয়, তখন তার ডান-সীমা = current index, আর বাঁ-সীমা = pop-এর পরে যে index top-এ থাকে। সাথে একটা sentinel (শেষে একটা `0`-উচ্চতার bar) যোগ করি যাতে loop শেষে stack-এ পড়ে থাকা সবাইকে pop করানো যায়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
increasing stack-এ যতক্ষণ বার উঁচু হতে থাকে, ততক্ষণ কেউ pop হয় না — তারা সবাই এখনো ডান দিকে আরও ছড়াতে পারে। যেই একটা খাটো bar আসে, সে stack-এর উপরের উঁচু bar-দের "তোমাদের ডান-সীমা পেয়ে গেছ" বলে pop করায়, আর তখনই তাদের ক্ষেত্রফল হিসাব হয়ে যায়। প্রতিটা bar একবার push, একবার pop → O(n)। index রাখায় প্রস্থ O(1)-তে বেরোয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: প্রতিটা জোড়া সীমানা `(i, j)`-র জন্য ওই অংশের সবচেয়ে খাটো bar বের করি, তারপর `min_height * (j - i + 1)` হিসাব করে সর্বোচ্চটা রাখি।
```text
best = 0
for i in range(n):
m = inf
for j in range(i, n):
m = min(m, heights[j])
best = max(best, m * (j - i + 1))
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুটো nested loop মানে O(n^2)-সংখ্যক অংশ, আর min চলমানভাবে রাখলেও মোট **O(n^2)**। `n = 10^5` হলে প্রায় 10^10 step — অসম্ভব। প্রতিটা bar-এর জন্য বাঁ/ডান-সীমা আলাদাভাবে বারবার খোঁজা পুরো অপচয়; monotonic stack এক pass-এ প্রতিটা bar-কে একবার ছুঁয়ে O(n)-তে দুই সীমাই দেয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: প্রতিটা সর্বোচ্চ আয়তক্ষেত্রের উচ্চতা কোনো একটা bar-এর সমান, আর সেই bar-ই ওই আয়তক্ষেত্রের সবচেয়ে খাটো। তাই সব আয়তক্ষেত্র দেখার দরকার নেই — শুধু "প্রতিটা bar যদি নিচু-সীমা হয় তবে সর্বোচ্চ কত চওড়া?" এই n-টা প্রশ্নের উত্তর হলেই চলে, আর সেটা previous/next-smaller।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
index-এর increasing stack রাখো; heights-এর শেষে একটা sentinel `0` যোগ করো। প্রতিটা `(i, h)`-তে: যতক্ষণ stack খালি নয় আর top-এর bar `h`-এর চেয়ে উঁচু, ততক্ষণ pop করো — pop-করা bar-এর উচ্চতা `H`, তার ডান-সীমা current `i`, বাঁ-সীমা pop-এর পরের top (`stack[-1]`, নাহলে `-1`); প্রস্থ `i - left - 1`, ক্ষেত্রফল `H * width`, max আপডেট করো। তারপর `i` push করো। sentinel `0` শেষে বাকি সবাইকে pop করিয়ে দেয়।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব সম্ভাব্য আয়তক্ষেত্র গুনব" — এভাবে ভেবো না (O(n^2))। বরং প্রতিটা bar-কে আলাদা করে জিজ্ঞেস করো — "আমি যদি সবচেয়ে খাটো হই, তবে বাঁয়ে-ডানে কতদূর আমার উচ্চতা ধরে ছড়াতে পারি?" এই উল্টো দৃষ্টিতে n-টা bar × O(1) করে = O(n), আর প্রতিটা আয়তক্ষেত্র ঠিক একবার (তার নিচু-সীমা bar-এর মাধ্যমে) গোনা হয়।
### ছবিতে বোঝা {#7-visual-explanation}
`heights = [2, 1, 5, 6, 2, 3]` (শেষে sentinel `0` জুড়ে), index-এর increasing stack (top ডানে):
```text
i h action stack(idx) area হিসাব
0 2 push [0] —
1 1 h[0]=2>1 pop0: H=2,L=-1,W=1-(-1)-1=1 -> 2 [1] 2
2 5 push [1,2] —
3 6 push [1,2,3] —
4 2 h[3]=6>2 pop3: H=6,L=2,W=4-2-1=1 -> 6
h[2]=5>2 pop2: H=5,L=1,W=4-1-1=2 -> 10 [1,4] 10 <- best
5 3 push [1,4,5] —
6 0 h[5]=3>0 pop5: H=3,L=4,W=6-4-1=1 -> 3
h[4]=2>0 pop4: H=2,L=1,W=6-1-1=4 -> 8
h[1]=1>0 pop1: H=1,L=-1,W=6-(-1)-1=6 -> 6 [6] max=10
```
H = pop-করা bar-এর উচ্চতা, L = pop-এর পর top index (নেই হলে -1), W = `i - L - 1`।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[2, 1, 2]` (sentinel দিয়ে `[2, 1, 2, 0]`):
1. `i=0 (2)`: push → `[0]`
2. `i=1 (1)`: `h[0]=2 > 1` → pop 0: `H=2`, left=-1, `W=1-(-1)-1=1`, area `2`, best=2; push 1 → `[1]`
3. `i=2 (2)`: `h[1]=1 > 2`? না; push 2 → `[1,2]`
4. `i=3 (0)`: `h[2]=2 > 0` → pop 2: `H=2`, left=1, `W=3-1-1=1`, area `2`, best=2; `h[1]=1 > 0` → pop 1: `H=1`, left=-1, `W=3-(-1)-1=3`, area `3`, best=3; push 3
5. return `best = 3`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def largest_rectangle_area(heights):
stack = [] # index রাখে; উচ্চতা নিচ->উপর বাড়তে থাকে
max_area = 0
extended = heights + [0] # শেষে sentinel 0 -> বাকি সবাইকে pop করায়
for i, h in enumerate(extended):
while stack and extended[stack[-1]] > h:
height = extended[stack.pop()] # এই bar-ই আয়তক্ষেত্রের নিচু-সীমা
left = stack[-1] if stack else -1 # বাঁয়ের previous-smaller
width = i - left - 1 # দুই সীমার মাঝের প্রস্থ
max_area = max(max_area, height * width)
stack.append(i)
return max_area
# ---- tests ----
assert largest_rectangle_area([2, 1, 5, 6, 2, 3]) == 10
assert largest_rectangle_area([2, 4]) == 4
assert largest_rectangle_area([6, 2, 5, 4, 5, 1, 6]) == 12
assert largest_rectangle_area([5]) == 5 # একটা bar
assert largest_rectangle_area([3, 3, 3]) == 9 # একই উচ্চতা, পুরো প্রস্থ
assert largest_rectangle_area([]) == 0 # খালি
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `stack = []` — index জমবে; উচ্চতা নিচ-থেকে-উপর increasing রাখা invariant।
- `extended = heights + [0]` — শেষে একটা `0`-উচ্চতার ভুয়া bar; এটা loop শেষে stack-এ পড়ে থাকা সব bar-কে pop করায় (আলাদা cleanup লাগে না)। মূল input বদলায় না।
- `while stack and extended[stack[-1]] > h:` — top-এর bar current-এর চেয়ে উঁচু মানে তার ডান-সীমা পাওয়া গেল।
- `height = extended[stack.pop()]` — pop-করা bar-ই এই আয়তক্ষেত্রের নিচু-সীমা (উচ্চতা)।
- `left = stack[-1] if stack else -1` — pop-এর পরের top-ই বাঁয়ের previous-smaller; কেউ না থাকলে `-1` (একদম বাঁ প্রান্ত পর্যন্ত)।
- `width = i - left - 1` — বাঁ-সীমা আর ডান-সীমা (`i`)-র মধ্যেকার পূর্ণ প্রস্থ।
- `max_area = max(...)` — এই bar-কে নিচু-সীমা ধরে সর্বোচ্চ ক্ষেত্রফল।
- `stack.append(i)` — current bar এখন stack-এ, ভবিষ্যতের ডান-সীমার অপেক্ষায়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`largest_rectangle_area([2,1,5,6,2,3])` → section 7-এর trace মতো index 4-এ `5` pop হওয়ার সময় `5*2 = 10` পাওয়া যায়, যা best। `largest_rectangle_area([3,3,3])` → কেউ pop হয় না যতক্ষণ sentinel আসে; তখন শেষ `3` থেকে শুরু করে প্রস্থ বাড়তে বাড়তে `1*3 + ...` হিসাবে সর্বোচ্চ `3*3 = 9`। সব assert pass করে শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function largestRectangleArea(heights) {
const stack = []; // index রাখে; উচ্চতা নিচ->উপর বাড়ে
let maxArea = 0;
const extended = [...heights, 0]; // শেষে sentinel 0 -> বাকি সবাইকে pop করায়
for (let i = 0; i < extended.length; i++) {
while (stack.length && extended[stack[stack.length - 1]] > extended[i]) {
const height = extended[stack.pop()]; // এই bar-ই নিচু-সীমা
const left = stack.length ? stack[stack.length - 1] : -1;
const width = i - left - 1; // দুই সীমার মাঝের প্রস্থ
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}
// ---- test cases ----
assert(largestRectangleArea([2, 1, 5, 6, 2, 3]) === 10, "main");
assert(largestRectangleArea([2, 4]) === 4, "two");
assert(largestRectangleArea([6, 2, 5, 4, 5, 1, 6]) === 12, "mid");
assert(largestRectangleArea([5]) === 5, "single");
assert(largestRectangleArea([3, 3, 3]) === 9, "equal");
assert(largestRectangleArea([]) === 0, "empty");
console.log("সব JS test pass!");
```
> **JS টীকা:** `[...heights, 0]` দিয়ে spread করে নতুন array বানাই — মূল input বদলায় না, আর শেষে একটা `0`-উচ্চতার sentinel যোগ হয় যা loop শেষে stack-এ পড়ে থাকা সব bar-কে pop করিয়ে ক্ষেত্রফল হিসাব করায়। `width = i - left - 1`-এর `-1`-টা গুরুত্বপূর্ণ; ভুলে `i - left` লিখলে এক ঘর বেশি গুনে answer ভুল হবে। `left` বের করতে stack খালি কিনা ternary দিয়ে দেখি (`-1` মানে একদম বাঁ প্রান্ত)।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function largestRectangleArea(heights: number[]): number {
const stack: number[] = []; // index রাখে
let maxArea = 0;
const extended: number[] = [...heights, 0]; // sentinel
for (let i = 0; i < extended.length; i++) {
while (stack.length && extended[stack[stack.length - 1]] > extended[i]) {
const height = extended[stack.pop()!];
const left = stack.length ? stack[stack.length - 1] : -1;
const width = i - left - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}
function expect