086 — Longest Subarray with Sum K (Positive)

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

Problem link ও উৎস

• 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 দৈর্ঘ্য)

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

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

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

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

চেনা উদাহরণে বোঝা

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

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

085 — Sliding Window Sum-এর কাঁধে। 085-এ window-র দৈর্ঘ্য স্থির (k), শুধু ডানে হাঁটত। এখানে দৈর্ঘ্য নিজেই বদলায় — তাই দুটো pointer (l, r) আলাদা করে রাখতে হয়:

• r প্রতি step-এ এগিয়ে নতুন element ঢোকায় (window বড় হয়)
• sum target ছাড়িয়ে গেলে l এগিয়ে বাঁ থেকে বের করে (window ছোট হয়)

085-এর "একটা ঢোকে, একটা বেরোয়" idea-টাই এখানে স্বাধীন দুই pointer-এ রূপ নিল। Fixed থেকে variable — এটাই এই note-এর লাফ।

ভেতরের অঙ্ক

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

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

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

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

সরল পথ — প্রতিটা শুরু থেকে প্রতিটা শেষ পর্যন্ত 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 করত না)।

কোথায় বেশি কাজ হতে পারে

দুটো 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 প্রতিটা শুরু থেকে আবার গুনছে, আগের কাজ ফেলে।

আরও ভালোভাবে ভাবা

মূল 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 নিশ্চিত কমে, তাই একসময় থামবেই।

ভাবনার পরিবর্তন

আসল "আহা!": sum কখনো target ছাড়িয়ে গেলে বাঁ থেকে কমাও — positive বলে কমানোই sum কমায়, কখনো বাড়ায় না, তাই window নিরাপদে হাঁটে।

আর while (not if) — কারণ একটা element ঢোকার পর sum অনেক বেশি হয়ে যেতে পারে, তখন একবারে নয়, কয়েকবার বাঁ থেকে বের করা লাগে। এই দুই — positive-এর গ্যারান্টি আর while-shrink — variable window-র প্রাণ।

ছবিতে বোঝা

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       আবার বড়

ছোট input-এ ধাপে ধাপে

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

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

উদাহরণ

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-এ দুই পথ মিলিয়ে দেখা হয়।

Output মিলিয়ে দেখা

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

উদাহরণ

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

খরচ ও সাধারণ ভুল

সময়

O(n) — r মোট n বার এগোয়; l-ও জীবনে বড়জোর n বার এগোয় (পিছায় না)। ভেতরের while ভয়ংকর দেখালেও মোট move ≤ 2n — এটাই amortized analysis।

অতিরিক্ত জায়গা

O(1) — শুধু l, s, best; বাড়তি কোনো array নেই।

যে ভুলগুলো এড়াতে হবে

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

শেখা ও পরের অনুশীলন

এই ধারণার পরের অনুশীলন

• 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)।

কৌশলটি মনে রাখুন

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।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে এক লাইনে: "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" লেখো।