Problem link ও উৎস
- **Original source:** Classic technique (contribution + monotonic stack spans)
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
- **Difficulty:** Hard
- **Pattern:** contribution + next/previous-smaller spans (monotonic stack)
- **Basic idea inherited from:** 076 — Sum of All Subarrays
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array `a` (দৈর্ঘ্য n) দেওয়া। প্রতিটা contiguous subarray-র **minimum** (সবচেয়ে ছোট element) বের করো, তারপর সেই minimum গুলোর **মোট যোগফল** চাই। সংখ্যা বড় হতে পারে, তাই উত্তর `10^9 + 7` দিয়ে mod করে দাও।
যেমন `a = [3, 1, 2, 4]`-এর subarray গুলোর minimum যোগ করলে মোট 17। তোমার কাজ এই যোগফল দ্রুত বের করা — প্রতিটা subarray ধরে min বের করে যোগ না করে।
### Input ও output {#6-example-input-and-output}
```text
a = [3, 1, 2, 4] -> 17
a = [11, 81, 94, 43, 3] -> 444 (LeetCode example)
a = [1, 2, 3, 4] -> 20
a = [4, 3, 2, 1] -> 20 (উল্টো দিকে একই, symmetric নয় তবু এখানে মিলল)
a = [2, 2, 2] -> 12 (সব সমান — tie সাবধানে!)
a = [1, 3, 1, 3, 1] -> 19 (একই মান বারবার)
```
সবচেয়ে গুরুত্বপূর্ণ edge case: **সমান মান (tie)।** `[2, 2, 2]`-এ যদি বাঁ আর ডান দুই দিকেই "≤" বা দুই দিকেই "<" ব্যবহার করো, একই subarray দুবার গোনা পড়বে বা বাদ পড়বে। সমাধান: **এক দিকে strictly-smaller, অন্য দিকে smaller-or-equal** — তাহলে সমান element-গুলোর মধ্যে প্রতিটা subarray ঠিক একবার গোনা হয়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো পাহাড়ি রাস্তায় পরপর কিছু খুঁটি, প্রতিটার উচ্চতা ভিন্ন। প্রতিটা খুঁটিকে জিজ্ঞেস করো: "তুমি কতদূর পর্যন্ত এলাকার সবচেয়ে ছোট খুঁটি?"
একটা খুঁটি বাঁ দিকে ততদূর "রাজত্ব" করে যতক্ষণ না তার চেয়ে খাটো কেউ আসে; ডান দিকেও তাই। এই বাঁ-দূরত্ব আর ডান-দূরত্ব গুণ করলে — সে কয়টা টানা অংশের (subarray) সবচেয়ে ছোট। সেই সব অংশে "সবচেয়ে ছোট"-এর হিসাবে তার উচ্চতাই গোনা হয়।
তাই মোট = প্রতিটা খুঁটির (উচ্চতা × কতগুলো অংশে সে সবচেয়ে ছোট)। খাটো খুঁটি অনেক অংশে রাজত্ব করে (দূর পর্যন্ত কেউ ছোট নেই), লম্বা খুঁটি অল্প — ঠিক এই কারণেই minimum-এর হিসাব এমন।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
মূলত **076 (Sum of All Subarrays)** থেকে — সেই "প্রতিটা element কয়টা subarray-তে আছে, সেই count × মান" চিন্তা। পার্থক্য: 076-এ count ছিল `(i+1)*(n-i)` (সব subarray), এখানে count শুধু "যেখানে সে minimum"।
আর নতুন হাতিয়ার **monotonic stack** — span (next/previous smaller) বের করার যন্ত্র, যার বিস্তারিত [../../04-stack-and-queue/](../../../04-stack-and-queue/README.md)-তে (যেমন Next Greater Element, Daily Temperatures)। contribution-এর কাঠামো 076 থেকে, span-এর কৌশল stack folder থেকে — দুটো মিলে এই Hard problem। তাই দুটোই আগে থাকা দরকার।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **contribution technique + span গোনা**। 076-এর মতো প্রতিটা element-এর অবদান গুনব, কিন্তু এবার শর্তসাপেক্ষে:
```text
a[i]-এর অবদান = a[i] × (কয়টা subarray-তে a[i]-ই minimum)
```
`a[i]` কয়টা subarray-তে minimum? যতদূর বাঁয়ে যাওয়া যায় যেখানে `a[i]`-এর চেয়ে ছোট কেউ নেই (`left` রকম শুরু), গুণ যতদূর ডানে (`right` রকম শেষ)। অর্থাৎ দরকার প্রতিটা i-এর **previous-smaller** আর **next-smaller** element-এর দূরত্ব। তারপর:
```text
উত্তর = Σ a[i] * left[i] * right[i] (mod 10^9 + 7)
```
এই span দ্রুত বের করার যন্ত্র monotonic stack — O(n)-এ সব previous/next smaller।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সব subarray ঘুরে প্রতিটার min বের করে যোগ। running min দিয়ে:
```python
def sum_subarray_mins_brute(a):
MOD = 10**9 + 7
n = len(a)
total = 0
for l in range(n):
m = a[l]
for r in range(l, n):
m = min(m, a[r]) # subarray (l..r)-এর running min
total += m
return total % MOD
```
সরল, ঠিক উত্তর — প্রতিটা শুরু `l`-এর জন্য `r` বাড়িয়ে min হালনাগাদ করে যোগ করে।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
দুটো nested loop, প্রায় `n²/2` subarray — **O(n²)**।
```text
n = 30000 হলে:
brute force: ~4.5 × 10^8 operation (O(n²)) — TLE
stack way : ~30000 operation (O(n) দুটো pass)
```
অপচয়টা: একই element নানা subarray-তে বারবার "min" হিসেবে গোনা হচ্ছে — অথচ "সে কয়টা subarray-তে min" এক স্প্যান-গোনায় বেরিয়ে আসে, প্রতিবার আলাদা না দেখে।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: প্রতি subarray-র min না খুঁজে, প্রতিটা element কয়টা subarray-তে min গোনো — সেটা `left[i] * right[i]`, যেখানে `left` = previous-smaller পর্যন্ত দূরত্ব, `right` = next-smaller পর্যন্ত দূরত্ব। span দুটো monotonic stack-এ O(n):
```python
def sum_subarray_mins(a):
MOD = 10**9 + 7
n = len(a)
prev_less = [-1] * n # previous strictly-smaller-এর index
next_le = [n] * n # next smaller-or-equal-এর index (tie ভাঙতে)
st = []
for i in range(n):
while st and a[st[-1]] >= a[i]:
st.pop()
prev_less[i] = st[-1] if st else -1
st.append(i)
st = []
for i in range(n - 1, -1, -1):
while st and a[st[-1]] > a[i]:
st.pop()
next_le[i] = st[-1] if st else n
st.append(i)
total = 0
for i in range(n):
left = i - prev_less[i]
right = next_le[i] - i
total += a[i] * left * right
return total % MOD
```
দুটো O(n) stack pass + একটা O(n) যোগ — মোট **O(n)**। O(n²) থেকে নেমে এল।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
দুটো "আহা!" মুহূর্ত এখানে।
প্রথম: **76-এর contribution-কে শর্তযুক্ত করো — "সব subarray"-র জায়গায় "যেখানে আমি minimum"।** count বদলে `(i+1)*(n-i)` থেকে `left * right` হয়, যেখানে span দুই দিকের nearest-smaller পর্যন্ত।
দ্বিতীয় (সবচেয়ে সূক্ষ্ম): **tie ভাঙো asymmetry দিয়ে — এক পাশে strict (`<`), অন্য পাশে non-strict (`≤`)।** সমান মানের element থাকলে, এই asymmetry নিশ্চিত করে প্রতিটা subarray-র min ঠিক একটা index-এ গোনা হয় (দুবার নয়, শূন্যবার নয়)। এই একটা সিদ্ধান্তই tie-bug-এর রক্ষাকবচ। (span বের করার যন্ত্র monotonic stack — stack folder-এর Next Greater Element-এরই আত্মীয়।)
### ছবিতে বোঝা {#5-visual-explanation}
`a = [3, 1, 2, 4]`। প্রতিটা element কতদূর বাঁয়ে-ডানে minimum:
```text
index: 0 1 2 3
a: [ 3 ] [ 1 ] [ 2 ] [ 4 ]
i=1 (মান 1, পুরো array-র সবচেয়ে ছোট):
বাঁয়ে: 1-এর চেয়ে ছোট কেউ নেই index 0 পর্যন্ত → শুরু-option {0,1} = 2 (left)
ডানে : 1-এর চেয়ে ছোট কেউ নেই শেষ পর্যন্ত → শেষ-option {1,2,3} = 3 (right)
1 minimum থাকে 2 × 3 = 6 টা subarray-তে → অবদান 1 × 6 = 6
প্রতিটা element-এর span আর অবদান:
index i: 0 1 2 3
a[i]: 3 1 2 4
left[i]: 1 2 1 1 ← বাঁয়ে শুরুর রকম (prev-smaller পর্যন্ত)
right[i]: 1 3 2 1 ← ডানে শেষের রকম (next-smaller পর্যন্ত)
অবদান: 3 6 4 4 ← a[i]*left*right
মোট = 3 + 6 + 4 + 4 = 17
```
মিলিয়ে দেখো (brute, প্রতি subarray-র min):
```text
[3]=3 [1]=1 [2]=2 [4]=4
[3,1]=1 [1,2]=1 [2,4]=2
[3,1,2]=1 [1,2,4]=1
[3,1,2,4]=1
যোগ = 3+1+2+4 + 1+1+2 + 1+1 + 1 = 17 ✓
```
মূল কথা: ছোট element (1) দূর পর্যন্ত "minimum-রাজত্ব" করে (6টা subarray), তাই বেশি অবদান। left × right = কয়টা subarray-তে সে min।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`a = [3, 1, 2, 4]`। প্রথমে previous-strictly-smaller (`prev_less`) আর next-smaller-or-equal (`next_le`):
```text
prev_less = [-1, -1, 1, 2] (index 0: বাঁয়ে ছোট নেই; index 2: বাঁয়ে ছোট index 1)
next_le = [ 1, 4, 4, 4] (index 0: ডানে ছোট/সমান index 1; বাকিদের শেষ পর্যন্ত নেই)
```
তারপর span আর অবদান:
| i | a[i] | prev_less | next_le | left = i−prev_less | right = next_le−i | অবদান a[i]·left·right |
| --- | --- | --- | --- | --- | --- | --- |
| 0 | 3 | -1 | 1 | 1 | 1 | 3 |
| 1 | 1 | -1 | 4 | 2 | 3 | 6 |
| 2 | 2 | 1 | 4 | 1 | 2 | 4 |
| 3 | 4 | 2 | 4 | 1 | 1 | 4 |
মোট = `3 + 6 + 4 + 4 = 17` ✓। element 1 সবচেয়ে ছোট, তাই সবচেয়ে বড় span (2×3=6) আর বড় অবদান।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def sum_subarray_mins(a):
"""সব subarray-র minimum-এর যোগফল (mod 1e9+7); contribution + monotonic stack, O(n)।
span: এক পাশে strictly-smaller, অন্য পাশে smaller-or-equal — tie ঠিক একবার গোনে।"""
MOD = 10**9 + 7
n = len(a)
prev_less = [-1] * n # previous strictly-smaller index
next_le = [n] * n # next smaller-or-equal index
st = []
for i in range(n):
while st and a[st[-1]] >= a[i]:
st.pop()
prev_less[i] = st[-1] if st else -1
st.append(i)
st = []
for i in range(n - 1, -1, -1):
while st and a[st[-1]] > a[i]:
st.pop()
next_le[i] = st[-1] if st else n
st.append(i)
total = 0
for i in range(n):
left = i - prev_less[i]
right = next_le[i] - i
total += a[i] * left * right
return total % MOD
def sum_subarray_mins_brute(a):
"""ধীর O(n^2) version — প্রতি subarray-র min যোগ; মিলিয়ে দেখার জন্য।"""
MOD = 10**9 + 7
n = len(a)
total = 0
for l in range(n):
m = a[l]
for r in range(l, n):
m = min(m, a[r])
total += m
return total % MOD
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert sum_subarray_mins([3, 1, 2, 4]) == 17
assert sum_subarray_mins([11, 81, 94, 43, 3]) == 444 # LeetCode example
assert sum_subarray_mins([1, 2, 3, 4]) == 20
assert sum_subarray_mins([4, 3, 2, 1]) == 20
assert sum_subarray_mins([2, 2, 2]) == 12 # tie — সাবধানে
assert sum_subarray_mins([1, 3, 1, 3, 1]) == 19 # একই মান বারবার
assert sum_subarray_mins([7]) == 7
# fast আর brute একই উত্তর কিনা (random brute-force cross-check, tie সহ):
import random
random.seed(29)
for _ in range(500):
arr = [random.randint(1, 6) for _ in range(random.randint(1, 12))] # ছোট রেঞ্জ = বহু tie
assert sum_subarray_mins(arr) == sum_subarray_mins_brute(arr)
print(sum_subarray_mins([3, 1, 2, 4])) # 17
print(sum_subarray_mins([11, 81, 94, 43, 3])) # 444
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
while st and a[st[-1]] >= a[i]:
st.pop()
prev_less[i] = st[-1] if st else -1
st.append(i)
```
বাঁ থেকে ডান pass — previous strictly-smaller খোঁজা। stack-এ index রাখি যাদের মান বাড়ন্ত; `a[i]`-এর চেয়ে বড়-বা-সমান সব pop (তাই বাকি থাকে কঠোরভাবে ছোট)। stack-এর top-ই previous-smaller, নাহলে -1।
```text
while st and a[st[-1]] > a[i]:
st.pop()
next_le[i] = st[-1] if st else n
```
ডান থেকে বাঁ pass — next smaller-or-equal খোঁজা। এখানে শুধু কঠোরভাবে বড় pop (`>`), তাই সমান element থেমে যায় — এই asymmetry-ই (এক পাশে `>=`, অন্য পাশে `>`) tie একবার গোনা নিশ্চিত করে।
```text
left = i - prev_less[i]
right = next_le[i] - i
total += a[i] * left * right
```
span: বাঁয়ে `left` রকম শুরু, ডানে `right` রকম শেষ। গুণ = `a[i]` কয়টা subarray-তে min; মান দিয়ে গুণ করে অবদান জমাই।
বাকি `assert` গুলো নির্দিষ্ট উদাহরণ + ছোট-রেঞ্জ random array (বহু tie) তে fast আর brute মিলিয়ে দেখছে (brute-force cross-check) — tie-handling ঠিক কিনা এখানেই যাচাই। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
`a = [3, 1, 2, 4]`:
- `prev_less = [-1, -1, 1, 2]`, `next_le = [1, 4, 4, 4]`
- অবদান: 3, 6, 4, 4
- মোট `17` → প্রথম `print`
- `[11, 81, 94, 43, 3]` → `444` → দ্বিতীয় `print`
- সব `assert` (tie সহ) pass → `সব test pass!`
ছাপা output:
```text
17
444
সব test pass!
```
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n)** — দুটো stack pass, প্রতিটায় প্রতিটা index ঠিক একবার push আর সর্বোচ্চ একবার pop (amortized O(1) per element), তারপর একটা O(n) যোগ। brute force-এর O(n²) থেকে বিশাল উন্নতি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(n)** — `prev_less`, `next_le` দুটো array আর stack (সর্বোচ্চ n element)। সবই O(n)।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **দুই পাশেই একই কঠোরতা (`<` বা `≤`) ব্যবহার** — সমান মান থাকলে subarray দুবার গোনা বা বাদ পড়ে। এক পাশে strict, অন্য পাশে non-strict — এটাই tie-এর #1 bug-রক্ষা।
2. **mod নিতে ভুলে যাওয়া** — যোগফল বিশাল হতে পারে; `% (10^9 + 7)` দিতে হবে (অন্য ভাষায় overflow-ও)।
3. **span গণনায় off-by-one** — `left = i - prev_less[i]`, `right = next_le[i] - i`; `prev_less`/`next_le`-এর sentinel (-1 আর n) এই দূরত্ব ঠিক রাখে।
4. **prev/next-smaller আর prev/next-greater গুলিয়ে ফেলা** — minimum-এর জন্য smaller লাগে; maximum-এর problem-এ greater (sign উল্টো)।
5. **brute-এ min প্রতিবার গোড়া থেকে বের করা** — running min না রাখলে brute O(n³); যাই হোক, বড় input-এ stack version ব্যবহার করো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Sum of Subarray Minimums** (