Problem link ও উৎস
- **Original source:** Classic monotonic-deque-on-prefix-sums exercise
- **Platform:** LeetCode —
- **Topic:** queue (monotonic deque) + prefix sums
- **Difficulty:** Hard
- **Pattern:** monotonic deque on prefix sums
- **Basic idea inherited from:** Problem 19-এর deque + math level 5-এর prefix sums — subarray-র যোগফলকে দুটো prefix-এর পার্থক্য বানিয়ে deque দিয়ে অপ্টিমাইজ করা
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা পূর্ণসংখ্যার array `nums` (ঋণাত্মক সংখ্যাও থাকতে পারে) আর একটা সংখ্যা `k` দেওয়া আছে। এমন **সবচেয়ে ছোট দৈর্ঘ্যের** contiguous subarray খুঁজতে হবে যার যোগফল **অন্তত `k`** (মানে `>= k`)। তেমন subarray না থাকলে `-1` ফেরত দাও।
```text
nums=[2,-1,2], k=3 -> 3 (পুরো [2,-1,2]=3, এর চেয়ে ছোট কিছু >=3 হয় না)
nums=[1], k=1 -> 1
nums=[1,2], k=4 -> -1 (কোনো subarray-র যোগ 4 ছোঁয় না)
```
ঋণাত্মক সংখ্যা থাকায় এটা সাধারণ "all-positive sliding window" দিয়ে হয় না — সেখানেই আসল চ্যালেঞ্জ।
### Input ও output {#8-example-input-and-output}
```text
Input : nums=[1], k=1 -> 1
Input : nums=[1,2], k=4 -> -1
Input : nums=[2,-1,2], k=3 -> 3
Input : nums=[84,-37,32,40,95], k=167 -> 3
Edge case 1 (negative k, negative nums): [-1,-2], k=-3 -> 1
Edge case 2 (পুরোটা লাগে) : [1,1,1], k=3 -> 3
Edge case 3 (প্রথম element-ই যথেষ্ট) : [5,1,1], k=5 -> 1
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি পাহাড়ি পথে হাঁটছ, প্রতি বিন্দুতে তোমার উচ্চতা = `prefix`। তুমি চাও এমন একটা শুরুর বিন্দু থেকে এখন পর্যন্ত নামা/ওঠা যেখানে উচ্চতার পার্থক্য অন্তত `k`, আর পথটা যত ছোট সম্ভব। তুমি শুধু সেই পুরোনো বিন্দুগুলো মনে রাখো যেগুলো ক্রমশ নিচু (increasing prefix-এর উল্টো দিক থেকে দেখলে) — কারণ একটা নতুন বিন্দু যদি আগের কোনো বিন্দুর সমান বা নিচু হয় আর কাছেও হয়, তবে পুরোনো উঁচু-দূরের বিন্দুটা আর কোনো কাজে লাগবে না, ফেলে দাও।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
দুটো জিনিসের মিলন। প্রথমত **prefix sums** (math level 5): subarray `(i, j)`-র যোগফল = `prefix[j] - prefix[i]`, যেখানে `prefix[t]` হলো প্রথম `t`-টা element-এর যোগফল। দ্বিতীয়ত **Problem 19-এর monotonic deque**: prefix array-র উপর একটা increasing deque চালিয়ে আমরা প্রতিটা `j`-র জন্য দ্রুত খুঁজি — এমন সবচেয়ে কাছের বাঁ-দিকের `i` যাতে `prefix[j] - prefix[i] >= k`।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
সমস্যাটা prefix-এ অনুবাদ করো: এমন `i < j` খোঁজো যাতে `prefix[j] - prefix[i] >= k`, আর `j - i` সবচেয়ে ছোট। অর্থাৎ একটা `j` ঠিক রেখে এমন `i` চাই যেটা (১) `prefix[i] <= prefix[j] - k` মানে, আর (২) `j`-এর যত কাছে সম্ভব।
deque-তে আমরা candidate index-দের রাখি, যাদের `prefix` মান **increasing**। দুটো নিয়ম এই invariant রক্ষা করে আর উত্তর দেয়:
- **Front থেকে answer:** front-এর `prefix[deque[0]]` সবচেয়ে ছোট; যদি `prefix[j] - prefix[deque[0]] >= k` হয়, তবে এই জোড়া বৈধ — দৈর্ঘ্য `j - deque[0]` রেকর্ড করো, আর front-কে popleft করো (এই `i` আর কোনো বড় `j`-র জন্য ছোট উত্তর দেবে না, কারণ `j` শুধু বাড়বে)।
- **Back থেকে maintenance:** নতুন `prefix[j]` যদি `prefix[deque[-1]]`-এর চেয়ে ছোট-বা-সমান হয়, তবে পুরোনো বড় back-টা চিরতরে useless — `j` একইসাথে নতুন (কাছে) আর ছোট (সহজে শর্ত মেটায়), তাই back pop করো।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **`collections.deque`** যেটা prefix array-র **index** রাখে, আর সেই index-গুলোর `prefix` মান increasing। সাথে একটা `prefix` array (দৈর্ঘ্য `n+1`)। deque লাগে কারণ দুই প্রান্তেই O(1) দরকার — front-এ answer তুলে popleft, back-এ useless pop।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রতিটা `j`-র জন্য আমরা চাই সবচেয়ে কাছের বৈধ `i` — front-এ ছোট prefix রাখলে সেটা সরাসরি পাওয়া যায়। আর back-এ বড় prefix রাখা অর্থহীন (নতুন ছোট prefix সবদিকে ভালো), তাই সেগুলো ছাঁটি। এই দুই-প্রান্তের ছাঁটাই deque ছাড়া সস্তায় হয় না; ফলে প্রতিটা index একবার push একবার pop → O(n)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: প্রতিটা শুরু `i`-র জন্য ডান দিকে যোগ করতে করতে প্রথম যেখানে চলমান যোগ `>= k`, সেই দৈর্ঘ্য রেকর্ড করি (ওই `i`-র জন্য ওটাই সবচেয়ে ছোট), সবার মধ্যে সর্বনিম্নটা রাখি।
```text
best = inf
for i in range(n):
s = 0
for j in range(i, n):
s += nums[j]
if s >= k:
best = min(best, j - i + 1)
break
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুটো nested loop → **O(n^2)**, `n = 10^5` হলে প্রায় 10^10 step — অসম্ভব। ঋণাত্মক সংখ্যার কারণে সাধারণ two-pointer sliding window-ও খাটে না (window ছোট করলে যোগফল আবার বেড়ে যেতে পারে)। তাই prefix sums + monotonic deque দিয়ে O(n)-তে নামাই।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
দুটো observation। **(১)** subarray-যোগ = দুই prefix-এর পার্থক্য, তাই সমস্যাটা "এমন কাছের ছোট prefix খোঁজো" হয়ে যায়। **(২)** যদি একটা পুরোনো index-এর prefix কোনো নতুন index-এর prefix-এর চেয়ে বড়-বা-সমান হয়, তবে পুরোনোটা চিরতরে অকেজো — নতুনটা ছোট (শর্ত সহজে মেটায়) আর কাছে (দৈর্ঘ্য কম)। তাই deque-তে শুধু increasing prefix রাখাই যথেষ্ট।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`prefix` array বানাও (`prefix[0]=0`, `prefix[t]=prefix[t-1]+nums[t-1]`)। একটা খালি deque নাও। প্রতিটা `j` (0 থেকে n) এর জন্য: **প্রথমে front-check** — যতক্ষণ deque খালি নয় আর `prefix[j] - prefix[deque[0]] >= k`, ততক্ষণ `best` আপডেট করে `popleft` করো। **তারপর back-maintain** — যতক্ষণ deque খালি নয় আর `prefix[deque[-1]] >= prefix[j]`, ততক্ষণ `pop` করো। শেষে `j` push করো। `best` কখনো না বদলালে `-1`।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** ঋণাত্মক সংখ্যায় "window বড়/ছোট করি" ভেবো না (ভেঙে পড়ে)। বরং সমস্যাটাকে prefix-এর জগতে নিয়ে যাও: প্রতিটা ডান-প্রান্ত `j`-র জন্য চাই একটা কাছের, যথেষ্ট-ছোট বাঁ-প্রান্ত `prefix`। তারপর deque দিয়ে দুটো জিনিস একসাথে করো — front থেকে বৈধ উত্তর তোলো, back থেকে চিরতরে-অকেজো বড় prefix ছাঁটো।
### ছবিতে বোঝা {#7-visual-explanation}
`nums=[2,-1,2], k=3` → `prefix=[0, 2, 1, 3]` (দৈর্ঘ্য 4)। deque index রাখে, `prefix` মান increasing:
```text
j prefix[j] front-check (>=k?) back-maintain deque(idx) best
0 0 deque খালি — [0] inf
1 2 2-prefix[0]=2 >=3? না prefix[0]=0<=2? রাখো [0,1] inf
2 1 1-prefix[0]=1 >=3? না prefix[1]=2>1 pop ->[0] [0,2] inf
prefix[0]=0<=1? রাখো
3 3 3-prefix[0]=3 >=3? হ্যাঁ -> len=3-0=3, popleft [2]
3-prefix[2]=2 >=3? না prefix[2]=1<=3? রাখো [2,3] 3
উত্তর: best=3
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `nums=[2,-1,2], k=3`, তাই `prefix=[0,2,1,3]`:
1. `j=0`: deque খালি; back-maintain কিছু না; push 0 → `[0]`
2. `j=1 (prefix 2)`: front `2-0=2 >= 3`? না। back: `prefix[0]=0 >= 2`? না। push 1 → `[0,1]`
3. `j=2 (prefix 1)`: front `1-0=1 >= 3`? না। back: `prefix[1]=2 >= 1`? হ্যাঁ → pop → `[0]`; `prefix[0]=0 >= 1`? না। push 2 → `[0,2]`
4. `j=3 (prefix 3)`: front `3-0=3 >= 3`? হ্যাঁ → `best=min(inf, 3-0)=3`, popleft → `[2]`; front `3-prefix[2]=3-1=2 >= 3`? না। back: `prefix[2]=1 >= 3`? না। push 3 → `[2,3]`
5. `best=3 <= n` → return `3`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import deque
def shortest_subarray(nums, k):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i] # prefix[t] = প্রথম t element-এর যোগ
dq = deque() # index into prefix; prefix মান increasing
best = n + 1 # "পাওয়া যায়নি" sentinel
for j in range(n + 1):
while dq and prefix[j] - prefix[dq[0]] >= k:
best = min(best, j - dq.popleft()) # বৈধ window; front সবচেয়ে কাছের ছোট start
while dq and prefix[dq[-1]] >= prefix[j]:
dq.pop() # prefix[j] ছোট ও নতুন -> পুরোনো বড়রা useless
dq.append(j)
return best if best <= n else -1
# ---- tests ----
def brute(nums, k): # সরল O(n^2) reference
n = len(nums)
best = n + 1
for i in range(n):
s = 0
for j in range(i, n):
s += nums[j]
if s >= k:
best = min(best, j - i + 1)
break
return best if best <= n else -1
assert shortest_subarray([1], 1) == 1
assert shortest_subarray([1, 2], 4) == -1
assert shortest_subarray([2, -1, 2], 3) == 3
assert shortest_subarray([84, -37, 32, 40, 95], 167) == 3
assert shortest_subarray([-1, -2], -3) == 1 # negative k ও nums
assert shortest_subarray([2, -1, 2], 3) == brute([2, -1, 2], 3)
assert shortest_subarray([84, -37, 32, 40, 95], 167) == brute([84, -37, 32, 40, 95], 167)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `prefix` লুপ — `prefix[t]` = প্রথম `t`-টা element-এর যোগ; subarray-যোগ `prefix[j]-prefix[i]`।
- `dq = deque()` — prefix-এর index রাখে; এদের `prefix` মান নিচ→উপর increasing।
- `best = n + 1` — "এখনো বৈধ subarray পাইনি"; বৈধ দৈর্ঘ্য কখনো `n`-এর বেশি হয় না, তাই `n+1` নিরাপদ sentinel।
- `while dq and prefix[j] - prefix[dq[0]] >= k:` — front-এর index দিয়ে subarray-যোগ `>= k` হলে এটা একটা বৈধ window; `j - dq.popleft()` দৈর্ঘ্য রেকর্ড করে front ফেলে দাও (এই start আর কোনো বড় `j`-তে ছোট উত্তর দেবে না)।
- `while dq and prefix[dq[-1]] >= prefix[j]:` / `dq.pop()` — নতুন prefix ছোট-বা-সমান হলে পুরোনো বড় back-রা চিরতরে useless, ছাঁটো; এতে deque increasing থাকে।
- `dq.append(j)` — current index candidate হিসেবে যোগ।
- `return best if best <= n else -1` — কোনো বৈধ window না পেলে `-1`।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`shortest_subarray([2,-1,2], 3)` → section 14-এর trace মতো `j=3`-এ front index 0 দিয়ে যোগ `3 >= 3`, দৈর্ঘ্য `3`, যা best। `shortest_subarray([1,2], 4)` → কোনো `j`-তেই front-check `>= 4` হয় না, `best` থাকে `n+1=3`, তাই `-1`। `brute` reference-এর সাথেও মিলে যায়। সব assert pass করে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — prefix বানাতে O(n); মূল loop-এ প্রতিটা index ঠিক একবার deque-তে push হয় আর বড়জোর একবার pop হয় (front বা back থেকে)। মোট deque operation ≤ 2(n+1)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — `prefix` array O(n), আর deque-তে সবচেয়ে খারাপ ক্ষেত্রে O(n) index।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- সাধারণ two-pointer sliding window দিয়ে চেষ্টা করা — ঋণাত্মক সংখ্যায় window সঙ্কুচিত করলে যোগ আবার বাড়তে পারে, তাই ভুল; prefix + deque লাগে।
- front-check আর back-maintain-এর ক্রম উল্টে দেওয়া — আগে front থেকে answer তোলা (পুরো deque ধরে), তারপর back ছাঁটা; ক্রম ভুল হলে কিছু উত্তর miss হতে পারে।
- back-maintain-এ `>` বনাম `>=` — `>=` দিলে সমান prefix-ও সরে, ফলে front-এ সবচেয়ে কাছের সমান-prefix থাকে (ছোট দৈর্ঘ্য); `>` রাখলেও ভুল হয় না কিন্তু `>=` পরিষ্কার।
- `prefix` array-র দৈর্ঘ্য `n` ধরা — `n+1` লাগে (`prefix[0]=0` সহ), নাহলে শুরু-থেকের subarray বাদ পড়ে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Problem 19-এর monotonic deque + math level 5-এর prefix sums; chapter-এর [../patterns.md](../patterns.md) Pattern 5-এর variant। পার্থক্য — fixed window নয়, বরং prefix-এর উপর deque চালিয়ে variable-length shortest খোঁজা, আর element front (answer) ও back (useless) দুদিক থেকেই বেরোয়।
### পরের অনুশীলন {#22-similar-harder-problems}
- Sliding Window Maximum (fixed-window deque) —