Problem link ও উৎস
- **Original source:** Classic exercise (longest subarray with given sum, positive numbers)
- **Platform:** Classic exercise —
- **Topic:** Sliding window → variable-size window (grow/shrink)
- **Difficulty:** Medium
- **Pattern:** grow/shrink window (শুঁয়োপোকা — ডান বাড়ে, বাঁ গুটায়)
- **Basic idea inherited from:** 085 — Sliding Window Sum (fixed → variable দৈর্ঘ্য)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা **positive** সংখ্যার array `a` আর একটা সংখ্যা `k` দেওয়া। এমন **সবচেয়ে লম্বা** পরপর subarray-র দৈর্ঘ্য বের করো যার যোগফল ঠিক `k`। না থাকলে 0।
মূল কথা: subarray পরপর হতে হবে (টুকরো টুকরো নয়), আর সব সংখ্যা positive — এই শর্তটাই window পথকে সম্ভব করে।
### Input ও output {#6-example-input-and-output}
```text
a k -> longest length (কোন subarray)
------------------------------------------------------------------
[1, 2, 3, 1, 1, 1, 1] 3 -> 3 [1, 1, 1]
[1, 2, 3] 6 -> 3 পুরোটা
[1, 1, 1, 1] 2 -> 2 যেকোনো [1, 1]
[5, 1, 2] 3 -> 2 [1, 2]
[1, 2, 3] 7 -> 0 এত sum হয় না
[4] 4 -> 1 [4]
```
Edge case: না মিললে 0; পুরো array-ই উত্তর হতে পারে; positive ধরে নেওয়া (negative হলে এই পথ অবৈধ)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা শুঁয়োপোকা পাতার উপর হাঁটছে আর তুমি চাও তার শরীর ঠিক `k` সেন্টিমিটার লম্বা থাকুক। সে মাথা (ডান প্রান্ত) সামনে বাড়ায় — শরীর লম্বা হয়। যদি `k`-এর চেয়ে লম্বা হয়ে যায়, সে লেজ (বাঁ প্রান্ত) গুটিয়ে আনে — শরীর ছোট হয়।
মাথা শুধু সামনে যায়, লেজও শুধু সামনে যায় — কেউ পেছায় না। ঠিক `k` দৈর্ঘ্য মিললে সেই মুহূর্তের লম্বা শরীরটা মনে রাখো। এই "মাথা বাড়াও, দরকারে লেজ গুটাও" ছন্দই variable window।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
**085 — Sliding Window Sum**-এর কাঁধে। 085-এ window-র দৈর্ঘ্য স্থির (`k`), শুধু ডানে হাঁটত। এখানে দৈর্ঘ্য **নিজেই বদলায়** — তাই দুটো pointer (`l`, `r`) আলাদা করে রাখতে হয়:
- `r` প্রতি step-এ এগিয়ে নতুন element ঢোকায় (window বড় হয়)
- sum target ছাড়িয়ে গেলে `l` এগিয়ে বাঁ থেকে বের করে (window ছোট হয়)
085-এর "একটা ঢোকে, একটা বেরোয়" idea-টাই এখানে স্বাধীন দুই pointer-এ রূপ নিল। Fixed থেকে variable — এটাই এই note-এর লাফ।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **monotonic window** — positive সংখ্যা বলে:
- ডানে element যোগ করলে window-র sum **সবসময় বাড়ে**
- বাঁ থেকে element বাদ দিলে sum **সবসময় কমে**
এই একমুখী আচরণের জন্যই "sum বেশি হলে বাঁ থেকে কমাও, কম হলে ডানে বাড়াও" নিরাপদে কাজ করে। Negative থাকলে যোগ করেও sum কমতে পারত, আর পুরো যুক্তি ভেঙে যেত।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরল পথ — প্রতিটা শুরু থেকে প্রতিটা শেষ পর্যন্ত subarray-র sum দেখা:
```python
def longest_sum_k_brute(a, k):
n = len(a)
best = 0
for i in range(n):
s = 0
for j in range(i, n):
s += a[j]
if s == k:
best = max(best, j - i + 1)
return best
```
ঠিক উত্তর দেয় — সব subarray-র sum যাচাই করে সবচেয়ে লম্বা মিলটা রাখে। negative-এও কাজ করত (কিন্তু window করত না)।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
দুটো nested loop — প্রায় n²/2 subarray। n = 100000 হলে প্রায় ৫০০ কোটি — Time Limit Exceeded।
```text
n = 100000 হলে:
brute force : ~5,000,000,000 subarray (O(n²))
sliding window: বড়জোর ~200000 move (O(n))
```
মূল অপচয়: positive বলে sum monotonic — তবু brute force প্রতিটা শুরু থেকে আবার গুনছে, আগের কাজ ফেলে।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: **positive বলে sum একমুখী — তাই একটা চলন্ত window রাখলেই হয়।**
```text
l = 0, s = 0
for r in range(n):
s += a[r] # মাথা এগোলো
while s > k: # বেশি হয়ে গেছে → লেজ গুটাও
s -= a[l]; l += 1
if s == k: # ঠিক মিলেছে
best = max(best, r - l + 1)
```
`s > k` হলে while দিয়ে যতক্ষণ দরকার বাঁ থেকে বের করি; positive বলে বের করলে sum নিশ্চিত কমে, তাই একসময় থামবেই।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!": **sum কখনো target ছাড়িয়ে গেলে বাঁ থেকে কমাও — positive বলে কমানোই sum কমায়, কখনো বাড়ায় না, তাই window নিরাপদে হাঁটে।**
আর `while` (not `if`) — কারণ একটা element ঢোকার পর sum অনেক বেশি হয়ে যেতে পারে, তখন একবারে নয়, কয়েকবার বাঁ থেকে বের করা লাগে। এই দুই — positive-এর গ্যারান্টি আর while-shrink — variable window-র প্রাণ।
### ছবিতে বোঝা {#5-visual-explanation}
`a = [1, 2, 3, 1, 1, 1, 1]`, `k = 3` — শুঁয়োপোকা হাঁটছে:
```text
a = [ 1 , 2 , 3 , 1 , 1 , 1 , 1 ]
r=0: [1] sum=1 <3 → মাথা বাড়াও
r=1: [1 2] sum=3 ✓ → দৈর্ঘ্য 2; মাথা বাড়াও
r=2: [1 2 3] sum=6 >3 → লেজ গুটাও: −1 → [2 3] sum=5>3 → −2 → [3] sum=3 ✓ দৈর্ঘ্য 1
r=3: [3 1] sum=4 >3 → −3 → [1] sum=1<3 → মাথা বাড়াও
r=4: [1 1] sum=2 <3
r=5: [1 1 1] sum=3 ✓ → দৈর্ঘ্য 3 ← সেরা!
r=6: [1 1 1 1] sum=4 >3 → −1 → [1 1 1] sum=3 ✓ দৈর্ঘ্য 3
সর্বোচ্চ দৈর্ঘ্য = 3
```
মাথা (`r`) আর লেজ (`l`) — দুজনেই শুধু ডানে:
```text
[==r বড় হলো
l==r] লেজ গুটিয়ে শর্ত ফেরাল
[====r আবার বড়
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`a = [1, 2, 3, 1, 1, 1, 1]`, `k = 3`। `l=0, s=0, best=0`:
| r | a[r] | s (যোগের পর) | while s>3 (বাঁ বের) | s, l পরে | s==3? | best |
| --- | --- | --- | --- | --- | --- | --- |
| 0 | 1 | 1 | — | s=1, l=0 | না | 0 |
| 1 | 2 | 3 | — | s=3, l=0 | হ্যাঁ (দৈর্ঘ্য 2) | 2 |
| 2 | 3 | 6 | −1(l→1), −2(l→2) | s=3, l=2 | হ্যাঁ (দৈর্ঘ্য 1) | 2 |
| 3 | 1 | 4 | −3(l→3) | s=1, l=3 | না | 2 |
| 4 | 1 | 2 | — | s=2, l=3 | না | 2 |
| 5 | 1 | 3 | — | s=3, l=3 | হ্যাঁ (দৈর্ঘ্য 3) | 3 |
| 6 | 1 | 4 | −1(l→4) | s=3, l=4 | হ্যাঁ (দৈর্ঘ্য 3) | 3 |
সর্বোচ্চ দৈর্ঘ্য **3** (`[1, 1, 1]`)। লক্ষ করো r=2-তে while দুবার চলল — `if` হলে window আধভাঙা থেকে যেত।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def longest_subarray_sum_k(a, k):
"""positive array a-তে যোগফল ঠিক k এমন সবচেয়ে লম্বা subarray-র দৈর্ঘ্য (না থাকলে 0)।"""
l = 0
s = 0
best = 0
for r in range(len(a)):
s += a[r] # মাথা এগোলো (window বড়)
while s > k and l <= r: # বেশি হলে লেজ গুটাও
s -= a[l]
l += 1
if s == k:
length = r - l + 1
if length > best:
best = length
return best
def longest_sum_k_brute(a, k):
"""ধীর reference — সব subarray-র sum যাচাই।"""
n = len(a)
best = 0
for i in range(n):
s = 0
for j in range(i, n):
s += a[j]
if s == k:
best = max(best, j - i + 1)
return best
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert longest_subarray_sum_k([1, 2, 3, 1, 1, 1, 1], 3) == 3
assert longest_subarray_sum_k([1, 2, 3], 6) == 3
assert longest_subarray_sum_k([1, 1, 1, 1], 2) == 2
assert longest_subarray_sum_k([5, 1, 2], 3) == 2
assert longest_subarray_sum_k([1, 2, 3], 7) == 0
assert longest_subarray_sum_k([4], 4) == 1
assert longest_subarray_sum_k([], 0) == 0
# brute force-এর সাথে মিলিয়ে দেখা (শুধু positive array, নানা random case)
import random
random.seed(19)
for _ in range(500):
n = random.randint(0, 12)
arr = [random.randint(1, 6) for _ in range(n)] # সব positive
k = random.randint(0, 20)
assert longest_subarray_sum_k(arr, k) == longest_sum_k_brute(arr, k), (arr, k)
print(longest_subarray_sum_k([1, 2, 3, 1, 1, 1, 1], 3)) # 3
print(longest_subarray_sum_k([1, 2, 3], 6)) # 3
print(longest_subarray_sum_k([1, 2, 3], 7)) # 0
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
l = 0 ; s = 0 ; best = 0
```
`l` লেজ (বাঁ প্রান্ত), `s` বর্তমান window-র sum, `best` সেরা দৈর্ঘ্য।
```text
for r in range(len(a)):
s += a[r]
```
`r` মাথা — প্রতি step-এ নতুন element ঢুকিয়ে window বড় করা।
```text
while s > k and l <= r:
s -= a[l]; l += 1
```
sum target ছাড়ালে বাঁ থেকে বের করে কমাও; positive বলে কমবেই, একসময় `s <= k` হবে। `while` কারণ একবারে নাও নামতে পারে।
```text
if s == k:
length = r - l + 1 ; best = max(best, length)
```
ঠিক মিললে বর্তমান window-র দৈর্ঘ্য মেপে সেরাটা রাখি।
`longest_sum_k_brute` test যাচাইয়ের reference; random positive case-এ দুই পথ মিলিয়ে দেখা হয়।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
3
3
0
সব test pass!
```
প্রথম লাইন `[1,1,1]`-এর দৈর্ঘ্য 3; দ্বিতীয় লাইন `[1,2,3]` পুরোটার যোগফল 6, দৈর্ঘ্য 3; তৃতীয় লাইন 7 হওয়ার subarray নেই → 0। তার আগে 500 random positive case brute-force-এর সাথে মিলেছে, তাই `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n)** — `r` মোট n বার এগোয়; `l`-ও জীবনে বড়জোর n বার এগোয় (পিছায় না)। ভেতরের while ভয়ংকর দেখালেও মোট move ≤ 2n — এটাই amortized analysis।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু `l`, `s`, `best`; বাড়তি কোনো array নেই।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **Negative number-এ এই পথ চালানো** — তখন যোগ করেও sum কমতে পারে, monotonicity ভাঙে; এই ক্ষেত্রে Level 5-এর prefix + hash map লাগে।
- **shrink-এ `if`, `while` না** — একটা element ঢোকার পর কয়েকবার বাঁ থেকে বের করা লাগতে পারে; `if` দিলে window আধভাঙা।
- **বাঁ বের করার সময় sum update ভুলে যাওয়া** — `l++` করলে `s -= a[l]`-ও করো; আগে বাদ, পরে pointer — ক্রম ঠিক রাখো।
- **দৈর্ঘ্যের সূত্র ভুল** — দৈর্ঘ্য `r − l + 1`, `r − l` নয়।
- **`s == k` চেক while-এর ভেতরে রাখা** — চেকটা shrink শেষ হওয়ার পরে, বাইরে; নাহলে ভুল দৈর্ঘ্য।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **GeeksforGeeks Longest Sub-Array with Sum K** (