Problem link ও উৎস
- **Original source:** LeetCode Minimum Size Subarray Sum
- **Platform:** LeetCode —
- **Topic:** Sliding window → shrinkable window (minimize length)
- **Difficulty:** Medium
- **Pattern:** shrinkable window (যত পারো লেজ গুটাও)
- **Basic idea inherited from:** 086 — Longest Subarray with Sum K (একই grow/shrink, তবে লক্ষ্য shortest)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা **positive** সংখ্যার array `a` আর একটা `target` দেওয়া। এমন **সবচেয়ে ছোট** পরপর subarray-র দৈর্ঘ্য বের করো যার যোগফল `>= target`। এমন subarray না থাকলে 0।
লক্ষ করো — এবার "ঠিক target" নয়, "target বা তার বেশি"। তাই sum target ছুঁলেই থামি না; বরং যত পারি ছোট করি, sum যতক্ষণ ≥ target থাকে।
### Input ও output {#6-example-input-and-output}
```text
a target -> min length (কোন subarray)
--------------------------------------------------------------
[2, 3, 1, 2, 4, 3] 7 -> 2 [4, 3]
[1, 1, 1, 1, 1, 1, 1] 11 -> 0 মোট sum 7 < 11
[1, 2, 3, 4, 5] 11 -> 3 [3, 4, 5]
[1, 4, 4] 4 -> 1 [4]
[5] 5 -> 1 [5]
[1, 2, 3] 7 -> 0 মোট 6 < 7
```
Edge case: পুরো array-র sum < target হলে 0; একটা element-ই ≥ target হলে দৈর্ঘ্য 1; positive ধরা।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তুমি কম পয়সায় ঠিক `target` ক্যালরি খেতে চাও — কিন্তু চাও **যত কম পদ** (subarray যত ছোট) তত ভালো। তুমি পরপর পদ যোগ করতে থাকো (মাথা বাড়াও); যেই ক্যালরি target ছুঁল, এবার পেছন থেকে পদ বাদ দিতে থাকো — যতক্ষণ ক্যালরি ≥ target থাকে।
যেই বাদ দিলে ক্যালরি target-এর নিচে নামবে, সেখানে থামো — ওটাই এই মুহূর্তের সবচেয়ে ছোট সম্ভব পদের দল। প্রতিবার এই সংখ্যাটা মনে রেখো, সবচেয়ে ছোটটা জিতবে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
**086 — Longest Subarray with Sum K**-এর কাঁধে — হুবহু একই grow/shrink কাঠামো। পার্থক্য শুধু **লক্ষ্য আর shrink-এর শর্ত**:
- **086**: sum **ঠিক k**; shrink করি যখন sum **>** k (বেশি হয়ে গেলে কমাই); সবচেয়ে **লম্বা** চাই
- **087**: sum **>= target**; shrink করি যখন sum **>=** target (ছুঁলেই ছোট করি); সবচেয়ে **ছোট** চাই
কাঠামো এক, কিন্তু "কখন shrink, আর কোন দৈর্ঘ্য রাখি" বদলে যায়। 086 (longest) আর 087 (shortest) পাশাপাশি পড়লে variable window-র দুই মুখই চেনা হয়ে যায়।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea আবারো **monotonic window** (positive সংখ্যা)। কিন্তু এবার শর্তটা `>=`:
- ডানে যোগ করলে sum বাড়ে → target ছোঁয়ার সম্ভাবনা বাড়ে
- বাঁ থেকে বাদ দিলে sum কমে → window ছোট হয়, কিন্তু ≥ target ধরে রাখতে হয়
target ছোঁয়ার পর আমরা **আক্রমণাত্মকভাবে** লেজ গুটাই — যতক্ষণ sum ≥ target থাকে, তত ছোট করি; প্রতিটা মুহূর্তে দৈর্ঘ্য মেপে সবচেয়ে ছোটটা রাখি।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরল পথ — প্রতিটা শুরু থেকে যোগ করতে করতে কখন target ছোঁয় দেখা:
```python
def min_subarray_brute(a, target):
n = len(a)
best = float('inf')
for i in range(n):
s = 0
for j in range(i, n):
s += a[j]
if s >= target:
best = min(best, j - i + 1)
break # আর বাড়ালে শুধু লম্বা হবে
return 0 if best == float('inf') else best
```
ঠিক উত্তর দেয় — প্রতিটা শুরু থেকে যত তাড়াতাড়ি target ছোঁয় সেই দৈর্ঘ্য নিয়ে সবচেয়ে ছোটটা রাখে।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
দুটো nested loop — সবচেয়ে খারাপ ক্ষেত্রে প্রায় n²/2। n = 100000 হলে প্রায় ৫০০ কোটি — Time Limit Exceeded।
```text
n = 100000 হলে:
brute force : ~5,000,000,000 step (O(n²))
sliding window: বড়জোর ~200000 move (O(n))
```
মূল অপচয়: positive বলে sum monotonic, একটা চলন্ত window-ই যথেষ্ট — তবু brute force প্রতিটা শুরু থেকে নতুন করে শুরু করছে।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: **একটা চলন্ত window রাখো; target ছুঁলে যত পারো বাঁ থেকে গুটিয়ে ছোট করো।**
```text
l = 0, s = 0, best = inf
for r in range(n):
s += a[r] # মাথা এগোলো
while s >= target: # ছুঁয়েছে → যত পারো ছোট করো
best = min(best, r - l + 1)
s -= a[l]; l += 1
return 0 if best == inf else best
```
খেয়াল করো — দৈর্ঘ্য মাপা হয় while-এর **ভেতরে**, কারণ shrink করতে করতে ছোট থেকে ছোট দৈর্ঘ্য পাওয়া যায়।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!": **target ছুঁলেই থেমো না — ≥ থাকা পর্যন্ত বাঁ থেকে গুটাতে থাকো, প্রতিটা ছোট দৈর্ঘ্য মেপে নাও; ঠিক যেখানে < হয়ে যাবে, সেটাই এই মুহূর্তের সীমা।**
086-এর সাথে তফাত: ওখানে দৈর্ঘ্য মাপতাম shrink-এর **পরে** (sum == k হলে), এখানে মাপি shrink-এর **ভেতরে** (≥ থাকতেই)। লক্ষ্য longest না shortest — তাই মাপার জায়গাটাই বদলে যায়। এই সূক্ষ্ম তফাতটাই দুই problem-এর আসল শিক্ষা।
### ছবিতে বোঝা {#5-visual-explanation}
`a = [2, 3, 1, 2, 4, 3]`, `target = 7` — শুঁয়োপোকা যত পারে ছোট হয়:
```text
a = [ 2 , 3 , 1 , 2 , 4 , 3 ]
r=0..3: [2 3 1 2] sum=8 ≥7 → দৈর্ঘ্য 4; লেজ গুটাও −2 → [3 1 2] sum=6 <7 থামো (best=4)
r=4: [3 1 2 4] sum=10 ≥7 → দৈর্ঘ্য 4; −3 → [1 2 4] sum=7 ≥7 দৈর্ঘ্য 3 (best=3); −1 → [2 4] sum=6<7 থামো
r=5: [2 4 3] sum=9 ≥7 → দৈর্ঘ্য 3; −2 → [4 3] sum=7 ≥7 দৈর্ঘ্য 2 (best=2)! −4 → [3] sum=3<7 থামো
সবচেয়ে ছোট দৈর্ঘ্য = 2 ([4, 3])
```
লক্ষ — target ছুঁলেই থামিনি; ≥ থাকা পর্যন্ত যত পেরেছি ছোট করেছি:
```text
[====r] ≥ target ছুঁল
[==r] লেজ গুটিয়ে আরো ছোট, এখনো ≥
[r] আর গুটালে < target → থামো, এই দৈর্ঘ্যটা ধরো
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`a = [2, 3, 1, 2, 4, 3]`, `target = 7`। `l=0, s=0, best=inf`:
| r | a[r] | s (যোগের পর) | while s≥7: দৈর্ঘ্য মাপি, বাঁ বের | s, l পরে | best |
| --- | --- | --- | --- | --- | --- |
| 0 | 2 | 2 | — | s=2, l=0 | inf |
| 1 | 3 | 5 | — | s=5, l=0 | inf |
| 2 | 1 | 6 | — | s=6, l=0 | inf |
| 3 | 2 | 8 | দৈর্ঘ্য 4(l=0); −2,l=1 → s=6<7 থামো | s=6, l=1 | 4 |
| 4 | 4 | 10 | দৈর্ঘ্য 4(l=1); −3,l=2 → s=7; দৈর্ঘ্য 3(l=2); −1,l=3 → s=6<7 | s=6, l=3 | 3 |
| 5 | 3 | 9 | দৈর্ঘ্য 3(l=3); −2,l=4 → s=7; দৈর্ঘ্য 2(l=4); −4,l=5 → s=3<7 | s=3, l=5 | 2 |
সবচেয়ে ছোট দৈর্ঘ্য **2** (`[4, 3]`)। লক্ষ করো r=5-এ দুবার দৈর্ঘ্য মাপলাম (3, তারপর 2) — ভেতরে মাপি বলেই ছোটটা ধরা পড়ল।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def min_subarray_len(a, target):
"""positive array a-তে sum >= target এমন সবচেয়ে ছোট subarray-র দৈর্ঘ্য (না থাকলে 0)।"""
l = 0
s = 0
best = float('inf')
for r in range(len(a)):
s += a[r] # মাথা এগোলো
while s >= target: # ছুঁয়েছে → যত পারো ছোট করো
length = r - l + 1
if length < best:
best = length
s -= a[l] # লেজ গুটাও
l += 1
return 0 if best == float('inf') else best
def min_subarray_brute(a, target):
"""ধীর reference — প্রতিটা শুরু থেকে যোগ করে যত তাড়াতাড়ি target ছোঁয়।"""
n = len(a)
best = float('inf')
for i in range(n):
s = 0
for j in range(i, n):
s += a[j]
if s >= target:
best = min(best, j - i + 1)
break
return 0 if best == float('inf') else best
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert min_subarray_len([2, 3, 1, 2, 4, 3], 7) == 2
assert min_subarray_len([1, 1, 1, 1, 1, 1, 1], 11) == 0
assert min_subarray_len([1, 2, 3, 4, 5], 11) == 3
assert min_subarray_len([1, 4, 4], 4) == 1
assert min_subarray_len([5], 5) == 1
assert min_subarray_len([1, 2, 3], 7) == 0
assert min_subarray_len([], 1) == 0
# brute force-এর সাথে মিলিয়ে দেখা (positive array, নানা random case)
import random
random.seed(23)
for _ in range(500):
n = random.randint(0, 12)
arr = [random.randint(1, 6) for _ in range(n)] # সব positive
tgt = random.randint(1, 25)
assert min_subarray_len(arr, tgt) == min_subarray_brute(arr, tgt), (arr, tgt)
print(min_subarray_len([2, 3, 1, 2, 4, 3], 7)) # 2
print(min_subarray_len([1, 2, 3, 4, 5], 11)) # 3
print(min_subarray_len([1, 2, 3], 7)) # 0
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
l = 0 ; s = 0 ; best = float('inf')
```
`l` লেজ, `s` window-র sum, `best` শুরুতে অসীম (এখনো কিছু পাইনি)।
```text
for r in range(len(a)):
s += a[r]
```
`r` মাথা — নতুন element ঢুকিয়ে window বড়।
```text
while s >= target:
length = r - l + 1 ; best = min(best, length)
s -= a[l] ; l += 1
```
হৃদয় — sum target ছুঁলে দৈর্ঘ্য মেপে (while-এর **ভেতরে**), তারপর বাঁ থেকে বের করে আরো ছোট করার চেষ্টা; positive বলে একসময় sum < target হয়ে while থামে।
```text
return 0 if best == float('inf') else best
```
কখনো target না ছুঁলে best অসীমই থাকবে → 0।
`min_subarray_brute` test যাচাইয়ের reference; random positive case-এ দুই পথ মিলিয়ে দেখা হয়।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
2
3
0
সব test pass!
```
প্রথম লাইন `[4,3]`-এর দৈর্ঘ্য 2; দ্বিতীয় লাইন `[3,4,5]`-এর দৈর্ঘ্য 3 (sum 12 ≥ 11); তৃতীয় লাইন মোট sum 6 < 7 → 0। তার আগে 500 random positive case brute-force-এর সাথে মিলেছে, তাই `সব test pass!`।
### JavaScript ও test cases {#21-javascript-solution-with-test-cases}
shrinkable window — sum ≥ target হলে while-এর ভেতরে দৈর্ঘ্য মেপে বাঁ গুটাও।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// smallest subarray length with sum >= target (0 if none), positive array
function minSubarrayLen(a, target) {
let l = 0, s = 0, best = Infinity;
for (let r = 0; r < a.length; r++) {
s += a[r]; // মাথা এগোলো
while (s >= target) { // ছুঁয়েছে -> যত পারো ছোট করো
best = Math.min(best, r - l + 1);
s -= a[l]; // লেজ গুটাও
l++;
}
}
return best === Infinity ? 0 : best;
}
// ---- test cases (example + edge) ----
assert(minSubarrayLen([2, 3, 1, 2, 4, 3], 7) === 2, "classic"); // [4,3]
assert(minSubarrayLen([1, 1, 1, 1, 1, 1, 1], 11) === 0, "unreachable"); // edge
assert(minSubarrayLen([1, 2, 3, 4, 5], 11) === 3, "mid");
assert(minSubarrayLen([1, 4, 4], 4) === 1, "single-elem");
assert(minSubarrayLen([5], 5) === 1, "one");
assert(minSubarrayLen([], 1) === 0, "empty"); // edge
console.log("সব JS test pass!");
```
> **JS টীকা:** "এখনো পাইনি" বোঝাতে `Infinity` ব্যবহার করো (Python-এর `float('inf')`-এর সমতুল্য), শেষে না-পেলে `0`। দৈর্ঘ্য অবশ্যই `while`-এর **ভেতরে** মাপো — shrink করতে করতেই সবচেয়ে ছোটটা ধরা পড়ে।
### TypeScript ও test cases {#22-typescript-solution-with-test-cases}
```typescript
function minSubarrayLen(a: number[], target: number): number {
let l = 0, s = 0;
let best: number = Infinity;
for (let r = 0; r < a.length; r++) {
s += a[r];
while (s >= target) {
best = Math.min(best, r - l + 1);
s -= a[l];
l++;
}
}
return best === Infinity ? 0 : best;
}
function expect