Problem link ও উৎস
- **Original source:** Classic monotonic-stack + contribution exercise
- **Platform:** LeetCode —
- **Topic:** stack (monotonic) + contribution counting
- **Difficulty:** Medium
- **Pattern:** monotonic stack + contribution technique
- **Basic idea inherited from:** math level 5-এর contribution technique (prefix-difference-contribution) — প্রতিটা element আলাদা করে জিজ্ঞেস করো "আমি কয়টা subarray-র min?", তারপর সব contribution যোগ করো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা সংখ্যার array `arr` দেওয়া আছে। তার **প্রতিটা** contiguous subarray ধরো, প্রতিটার ভেতরের সবচেয়ে ছোট সংখ্যাটা (minimum) বের করো, আর সেই সব minimum যোগ করো। উত্তর বড় হতে পারে, তাই `10**9 + 7` দিয়ে modulo নিয়ে ফেরত দাও।
`arr = [3, 1, 2, 4]`-এর জন্য সব subarray আর তাদের min দেখো:
```text
[3] -> 3
[3,1] -> 1
[3,1,2] -> 1
[3,1,2,4] -> 1
[1] -> 1
[1,2] -> 1
[1,2,4] -> 1
[2] -> 2
[2,4] -> 2
[4] -> 4
যোগফল = 3+1+1+1+1+1+1+2+2+4 = 17
```
### Input ও output {#8-example-input-and-output}
```text
Input : [3, 1, 2, 4] -> Output: 17
Input : [11, 81, 94, 43, 3] -> Output: 444
Input : [2, 2, 2] -> Output: 12 (6 subarray, প্রতিটার min 2)
Edge case 1 (একটা element) : [7] -> 7
Edge case 2 (কঠোর বাড়তি) : [1, 2, 3] -> 1*6 + 2*2 + 3*1... = 10
Edge case 3 (কঠোর কমতি) : [3, 2, 1] -> প্রতিটা suffix-এর শেষজনই min
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একদল মানুষ পাশাপাশি দাঁড়িয়ে, প্রত্যেকের একটা উচ্চতা আছে, আর "সবচেয়ে খাটো লোকই দলের নেতা" — এই নিয়ম। প্রতিটা লোককে জিজ্ঞেস করো: "তুমি বাঁ দিকে কতদূর আর ডান দিকে কতদূর পর্যন্ত নেতা থাকতে পারো, যতক্ষণ না তোমার চেয়ে খাটো কেউ এসে পড়ছে?" সেই বাঁ-পরিসর আর ডান-পরিসর গুণ করলেই পাও — এই লোকটা কয়টা সম্ভাব্য দলের নেতা। সবার "নেতাগিরির হিসাব" যোগ করলেই মোট উত্তর।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **contribution technique**-এর সরাসরি প্রয়োগ (math level 5, prefix-difference-contribution)। মূল মন্ত্র: পুরো যোগফলকে subarray-ধরে-ধরে না ভেবে, **element-ধরে-ধরে** ভাবো। প্রশ্নটা উল্টে জিজ্ঞেস করো — "প্রতিটা `arr[i]` কয়টা subarray-র minimum হয়?" সেই সংখ্যাটা `count[i]` হলে পুরো উত্তর হলো `sum(arr[i] * count[i])`।
আর `count[i]` বের করতে লাগে **monotonic stack** (Problem 9, 16-এর machinery): বাঁয়ে আর ডানে `arr[i]`-এর "শাসন এলাকা" (যেখানে সে min থাকে) কতদূর ছড়ায়, সেটা previous/next-smaller দিয়ে মাপা যায়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: একটা subarray-তে `arr[i]` ঠিক তখনই min, যখন subarray-টা পুরোপুরি `arr[i]`-এর "এলাকা"-র ভেতরে থাকে আর `i`-কে ছুঁয়ে থাকে। এই এলাকা বাঁ দিকে থামে সেই index-এ যেখানে প্রথম arr[i]-এর চেয়ে ছোট কেউ আছে, ডান দিকেও তাই।
ধরা যাক:
- `left` = `i` থেকে শুরু করে বাঁ দিকে কয়টা শুরু-বিন্দু বাছা যায় যেখানে `arr[i]` এখনো min থাকে।
- `right` = `i` থেকে ডান দিকে কয়টা শেষ-বিন্দু বাছা যায়।
তাহলে `arr[i]`-কে min রাখা subarray-র সংখ্যা = `left * right` (বাঁ পছন্দ আর ডান পছন্দ স্বাধীন, তাই গুণ)। contribution = `arr[i] * left * right`।
**সমান সংখ্যার ফাঁদ:** array-তে সমান সংখ্যা থাকলে দুটো element একই subarray-র "min" হিসেবে দুবার গোনা হয়ে যেতে পারে। এটা ঠেকাতে এক পাশে **strictly** ছোট খুঁজি (`<`), অন্য পাশে **ছোট-বা-সমান** (`<=`) — তাহলে প্রতিটা subarray ঠিক একজনের দখলেই পড়ে, double-count হয় না।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **monotonic stack** (Python-এ `list`) যেখানে index রাখি — দুবার ব্যবহার করি: একবার বাঁ-থেকে-ডান scan-এ `prev_less` (previous strictly-smaller) বের করতে, আরেকবার ডান-থেকে-বাঁ scan-এ `next_le` (next smaller-or-equal) বের করতে। সাথে দুটো array এই দূরত্বগুলো ধরে রাখে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
"প্রতিটা element-এর জন্য বাঁ/ডানে প্রথম ছোট প্রতিবেশী" — এটা monotonic stack-এর হুবহু কাজ (Pattern 4)। প্রতিটা index stack-এ একবার ঢোকে আর বড়জোর একবার বের হয়, তাই দুটো pass-ই O(n)। contribution technique এর সাথে মিলে পুরো O(n^2)-সংখ্যক subarray-কে গোনার বদলে আমরা প্রতিটা element-কে একবার করে ছুঁয়ে কাজ সারি।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সবচেয়ে সরল চিন্তা: প্রতিটা শুরু `i`-র জন্য ডান দিকে এগোতে এগোতে চলমান min রাখো, আর প্রতিটা শেষ `j`-তে সেই min যোগফলে যোগ করো।
```text
total = 0
for i in range(n):
m = inf
for j in range(i, n):
m = min(m, arr[j])
total += m
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুটো nested loop মানে O(n^2)-সংখ্যক subarray, প্রতিটার জন্য O(1) কাজ হলেও মোট **O(n^2)**। n বড় হলে (যেমন 30000) এটা প্রায় 9*10^8 step — সময়ে আটকে যাবে। আমরা চাই প্রতিটা element-কে একবার ছুঁয়ে O(n)-তে কাজ শেষ করতে, আর সেটাই contribution + monotonic stack দেয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: subarray গুনে min যোগ করার বদলে, প্রতিটা **element কয়বার min হিসেবে গোনা হবে** সেটা সরাসরি বের করা যায়। `arr[i]` min থাকে ঠিক ততক্ষণ যতক্ষণ subarray-টা বাঁয়ে previous-smaller আর ডানে next-smaller পার না করে। এই দুই সীমানা monotonic stack এক pass-এ দিয়ে দেয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
দুটো pass চালাও। প্রথমে বাঁ-থেকে-ডান একটা stack রেখে প্রতিটা `i`-র `prev_less[i]` (বাঁয়ের শেষ strictly ছোট index) বের করো — stack-এ `arr[stack[-1]] >= arr[i]` যতক্ষণ, pop করো; যা টেকে তার top-ই previous-smaller। তারপর ডান-থেকে-বাঁ আরেকটা stack রেখে `next_le[i]` (ডানের পরের ছোট-বা-সমান index) বের করো — এবার `arr[stack[-1]] > arr[i]` যতক্ষণ pop। শেষে প্রতিটা `i`-র জন্য `left = i - prev_less[i]`, `right = next_le[i] - i`, আর `arr[i] * left * right` যোগ করো।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব subarray ঘুরে min যোগ করব" — এই দিক থেকে ভেবো না। উল্টে ভাবো — "প্রতিটা সংখ্যা মোট যোগফলে **কতটা contribute** করে?" একটা সংখ্যা `v` যতগুলো subarray-র min, ততবার `v` যোগফলে ঢোকে। তাই কাজটা হয়ে যায় "প্রতিটা v কয়বার min" গোনা — সেটাই বাঁ-পরিসর × ডান-পরিসর। strict/non-strict অসমতা দিয়ে সমান সংখ্যার double-count আটকাও।
### ছবিতে বোঝা {#7-visual-explanation}
`arr = [3, 1, 2, 4]`-এ প্রতিটা element-এর এলাকা (`left` = বাঁ পরিসর, `right` = ডান পরিসর):
```text
idx val prev_less(<) next_le(<=) left=i-PL right=NL-i count=L*R contri=val*count
0 3 -1 1 1 1 1 3
1 1 -1 4 (n) 2 3 6 6
2 2 1 4 (n) 1 2 2 4
3 4 2 4 (n) 1 1 1 4
মোট contribution = 3+6+4+4 = 17
```
PL = previous strictly-smaller-এর index (নেই হলে -1); NL = next smaller-or-equal-এর index (নেই হলে n=4)।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[3, 1, 2, 4]`:
1. **prev_less pass** (বাঁ→ডান, `>=` হলে pop): `i=0` → stack খালি, `prev_less[0]=-1`, push 0; `i=1(1)` → 3>=1 pop 0, খালি, `prev_less[1]=-1`, push 1; `i=2(2)` → 1>=2? না, `prev_less[2]=1`, push 2; `i=3(4)` → 2>=4? না, `prev_less[3]=2`, push 3. → `prev_less = [-1,-1,1,2]`
2. **next_le pass** (ডান→বাঁ, `>` হলে pop): `i=3` → খালি, `next_le[3]=4`, push 3; `i=2(2)` → 4>2 pop 3, খালি, `next_le[2]=4`, push 2; `i=1(1)` → 2>1 pop 2, খালি, `next_le[1]=4`, push 1; `i=0(3)` → 1>3? না, `next_le[0]=1`, push 0. → `next_le = [1,4,4,4]`
3. **contribution:** `left=[1,2,1,1]`, `right=[1,3,2,1]` → `3*1*1 + 1*2*3 + 2*1*2 + 4*1*1 = 3+6+4+4 = 17`
4. `17 % (10**9+7) = 17` → return `17`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def sum_subarray_mins(arr):
MOD = 10**9 + 7
n = len(arr)
prev_less = [-1] * n # বাঁয়ে শেষ strictly-ছোট element-এর index
stack = []
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]: # >= : strict-less বাঁয়ে রাখি
stack.pop()
prev_less[i] = stack[-1] if stack else -1
stack.append(i)
next_le = [n] * n # ডানে পরের ছোট-বা-সমান element-এর index
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] > arr[i]: # > : ছোট-বা-সমান ডানে রাখি
stack.pop()
next_le[i] = stack[-1] if stack else n
stack.append(i)
total = 0
for i in range(n):
left = i - prev_less[i] # i-তে শেষ হওয়া কয়টা subarray-তে arr[i] min
right = next_le[i] - i # i-তে শুরু হওয়া কয়টা subarray-তে arr[i] min
total += arr[i] * left * right
return total % MOD
# ---- tests ----
def brute(arr): # সরল কিন্তু ধীর O(n^2) reference
total = 0
for i in range(len(arr)):
m = arr[i]
for j in range(i, len(arr)):
m = min(m, arr[j])
total += m
return total % (10**9 + 7)
assert sum_subarray_mins([3, 1, 2, 4]) == 17
assert sum_subarray_mins([11, 81, 94, 43, 3]) == 444
assert sum_subarray_mins([7]) == 7 # একটা element
assert sum_subarray_mins([2, 2, 2]) == 12 # সব সমান -> double-count নেই
assert sum_subarray_mins([5, 4, 3, 2, 1]) == brute([5, 4, 3, 2, 1])
assert sum_subarray_mins([3, 1, 2, 4]) == brute([3, 1, 2, 4])
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `MOD = 10**9 + 7` — যোগফল বড় হতে পারে, তাই শেষে modulo।
- `prev_less` pass — প্রতিটা `i`-র জন্য বাঁয়ের শেষ **strictly** ছোট index; `>=` দেখলে pop করি যাতে সমান সংখ্যাও সরে যায় (strict-less টেকে)।
- `next_le` pass — ডান-থেকে-বাঁ গিয়ে ডানের পরের **ছোট-বা-সমান** index; এখানে `>` দেখলে pop, তাই সমান সংখ্যা টিকে থাকে (non-strict)। এই strict/non-strict অসমতাই double-count আটকায়।
- `left = i - prev_less[i]` / `right = next_le[i] - i` — বাঁ আর ডান দিকের শাসন-পরিসর।
- `total += arr[i] * left * right` — এই element কয়টা subarray-র min (`left*right`), তত গুণ তার value যোগফলে।
- `return total % MOD` — চূড়ান্ত উত্তর modulo করে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`sum_subarray_mins([3,1,2,4])` → section 7-এর table মতো contribution `3,6,4,4`, যোগফল `17`। `sum_subarray_mins([2,2,2])` → strict/non-strict জোড়ার কারণে তিনটা `2` মিলে ঠিক `12` (6 subarray × min 2), কোনো subarray দুবার গোনা হয় না। `brute` reference-এর সাথেও মিলে যায়। সব assert pass করে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — দুটো monotonic-stack pass আর একটা contribution pass, প্রতিটা O(n); প্রতিটা index বড়জোর একবার push আর একবার pop হয়।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — `prev_less`, `next_le` দুটো array আর stack, সবচেয়ে খারাপ ক্ষেত্রে stack-এ n-টা index।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- দুই পাশেই একই অসমতা ব্যবহার করা (দুদিকেই `<` বা দুদিকেই `<=`) — সমান সংখ্যা থাকলে subarray গুলো double-count বা miss হয়; এক পাশে strict, আরেক পাশে non-strict লাগবে।
- শেষে modulo না নেওয়া — বড় array-তে overflow না হলেও LeetCode ভুল উত্তর ধরবে।
- `prev_less`/`next_le`-তে "নেই" ক্ষেত্রের sentinel ভুল দেওয়া (`-1` আর `n`) — তাহলে পরিসরের হিসাব এক ঘর এদিক-ওদিক হয়ে যায়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: math level 5-এর **contribution technique** (prefix-difference-contribution) আর chapter-এর [../patterns.md](../patterns.md) Pattern 4 (Monotonic Stack)। Problem 9 (daily temperatures) আর 16 (stock span)-এর previous/next-smaller machinery এখানে দুবার ব্যবহার হয়, শুধু উত্তরটা distance নয় — পরিসরের গুণফল।
### পরের অনুশীলন {#22-similar-harder-problems}
- Sum of Subarray Ranges (max-min, দুটো contribution) —