086 — Longest Subarray with Sum K (Positive)¶

085-এ window-র দৈর্ঘ্য ছিল ঠিক k, বদলাত না। এখানে প্রথমবার window নিজের আকার বদলাবে — ডান প্রান্ত এগোয়, শর্ত ভাঙলে বাঁ প্রান্ত গুটিয়ে আসে। একে বলি variable sliding window বা আদর করে শুঁয়োপোকা। একটা গুরুত্বপূর্ণ শর্ত আছে — সব সংখ্যা positive হতে হবে, নাহলে এই যুক্তি ভেঙে পড়ে। কেন, সেটাও বুঝবে। ধীরে পড়ো।

Source¶

Original source: Classic exercise (longest subarray with given sum, positive numbers)
Platform: Classic exercise — https://www.geeksforgeeks.org/longest-sub-array-sum-k/
Topic: Sliding window → variable-size window (grow/shrink)
Difficulty: Medium
Pattern: grow/shrink window (শুঁয়োপোকা — ডান বাড়ে, বাঁ গুটায়)
Basic idea inherited from: 085 — Sliding Window Sum (fixed → variable দৈর্ঘ্য)

1. Problem in simple words¶

একটা positive সংখ্যার array a আর একটা সংখ্যা k দেওয়া। এমন সবচেয়ে লম্বা পরপর subarray-র দৈর্ঘ্য বের করো যার যোগফল ঠিক k। না থাকলে 0।

মূল কথা: subarray পরপর হতে হবে (টুকরো টুকরো নয়), আর সব সংখ্যা positive — এই শর্তটাই window পথকে সম্ভব করে।

2. What is the math idea?¶

মূল idea হলো monotonic window — positive সংখ্যা বলে:

ডানে element যোগ করলে window-র sum সবসময় বাড়ে
বাঁ থেকে element বাদ দিলে sum সবসময় কমে

এই একমুখী আচরণের জন্যই "sum বেশি হলে বাঁ থেকে কমাও, কম হলে ডানে বাড়াও" নিরাপদে কাজ করে। Negative থাকলে যোগ করেও sum কমতে পারত, আর পুরো যুক্তি ভেঙে যেত।

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-এর লাফ।

4. Real-life analogy¶

ভাবো একটা শুঁয়োপোকা পাতার উপর হাঁটছে আর তুমি চাও তার শরীর ঠিক k সেন্টিমিটার লম্বা থাকুক। সে মাথা (ডান প্রান্ত) সামনে বাড়ায় — শরীর লম্বা হয়। যদি k-এর চেয়ে লম্বা হয়ে যায়, সে লেজ (বাঁ প্রান্ত) গুটিয়ে আনে — শরীর ছোট হয়।

মাথা শুধু সামনে যায়, লেজও শুধু সামনে যায় — কেউ পেছায় না। ঠিক k দৈর্ঘ্য মিললে সেই মুহূর্তের লম্বা শরীরটা মনে রাখো। এই "মাথা বাড়াও, দরকারে লেজ গুটাও" ছন্দই variable window।

5. Visual explanation¶

a = [1, 2, 3, 1, 1, 1, 1], k = 3 — শুঁয়োপোকা হাঁটছে:

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) — দুজনেই শুধু ডানে:

[==r              বড় হলো
   l==r]          লেজ গুটিয়ে শর্ত ফেরাল
      [====r       আবার বড়

6. Example input and output¶

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 হলে এই পথ অবৈধ)।

7. Brute force thinking¶

সরল পথ — প্রতিটা শুরু থেকে প্রতিটা শেষ পর্যন্ত subarray-র sum দেখা:

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।

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 রাখলেই হয়।

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-র প্রাণ।

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 আধভাঙা থেকে যেত।

12. Python solution¶

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¶

l = 0 ; s = 0 ; best = 0

l লেজ (বাঁ প্রান্ত), s বর্তমান window-র sum, best সেরা দৈর্ঘ্য।

for r in range(len(a)):
    s += a[r]

r মাথা — প্রতি step-এ নতুন element ঢুকিয়ে window বড় করা।

    while s > k and l <= r:
        s -= a[l]; l += 1

sum target ছাড়ালে বাঁ থেকে বের করে কমাও; positive বলে কমবেই, একসময় s <= k হবে। while কারণ একবারে নাও নামতে পারে।

    if s == k:
        length = r - l + 1 ; best = max(best, length)

ঠিক মিললে বর্তমান window-র দৈর্ঘ্য মেপে সেরাটা রাখি।

longest_sum_k_brute test যাচাইয়ের reference; random positive case-এ দুই পথ মিলিয়ে দেখা হয়।

14. Output walkthrough¶

চালালে ছাপবে:

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!।

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 শেষ হওয়ার পরে, বাইরে; নাহলে ভুল দৈর্ঘ্য।

18. Harder problems that inherit this idea¶

GeeksforGeeks Longest Sub-Array with Sum K (https://www.geeksforgeeks.org/longest-sub-array-sum-k/) — এই problem-এরই মূল রূপ (positive ও general দুই variant)।
LeetCode Minimum Size Subarray Sum (https://leetcode.com/problems/minimum-size-subarray-sum/) — একই variable window, তবে longest নয় shortest (এই repo-র 087)।
LeetCode Subarray Product Less Than K (https://leetcode.com/problems/subarray-product-less-than-k/) — যোগের বদলে গুণ, একই grow/shrink (090)।

19. Pattern learned¶

Variable sliding window (grow/shrink) on positive values — r বাড়াও; s > k হলে while দিয়ে l থেকে বের করো; s == k-এ answer update। বড় শিক্ষা: positive মানে sum monotonic — তখনই window পথ বৈধ; negative এলে prefix + hash map।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "positive array + 'sum ঠিক k' = শুঁয়োপোকা window; r বাড়াও, বেশি হলে while দিয়ে l গুটাও, মিললে দৈর্ঘ্য রাখো। Signal: 'positive' আর 'subarray sum' একসাথে দেখলে variable window; negative দেখলেই থামো — prefix+hash।"

পরের ধাপ → 087 — Minimum Size Subarray Sum (এবার সবচেয়ে ছোট window)। ভিত্তি → 085 — Sliding Window Sum।

ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।