085 — Sliding Window Sum¶

এতক্ষণ দুটো আঙুল নিয়ে খেলেছ; এবার একটা জানালা (window)। এই note-টা sliding window-র হাতেখড়ি — সবচেয়ে সহজ রূপ: ঠিক k দৈর্ঘ্যের একটা জানালা array-র উপর দিয়ে ডানে হাঁটবে। মূল জাদু একটাই — জানালা সরালে পুরো sum আবার গোনার দরকার নেই, শুধু একটা ঢোকে আর একটা বেরোয়। ছোট কিন্তু শক্তিশালী — পরের সব window problem এই ভিতের উপর দাঁড়াবে।

Source¶

Original source: Classic exercise (fixed-size sliding window)
Platform: Classic exercise — https://www.geeksforgeeks.org/window-sliding-technique/
Topic: Sliding window → fixed-size window, incremental sum
Difficulty: Easy
Pattern: fixed window (একটা ঢোকে, একটা বেরোয়)
Basic idea inherited from: 067 — Prefix Sum (running sum ধরে রাখা; window হলো তার চলমান রূপ)

1. Problem in simple words¶

একটা array a আর একটা সংখ্যা k দেওয়া। ঠিক k টা পরপর element নিয়ে যে subarray হয় তাদের যোগফলের মধ্যে সর্বোচ্চ যোগফলটা বের করো (চাইলে সব window-র sum-ও বের করা যায়)।

মানে array-র উপর k দৈর্ঘ্যের একটা জানালা বসিয়ে এক ঘর করে ডানে সরাতে থাকো; প্রতিবার window-র ভেতরের যোগফল দেখো, সর্বোচ্চটা রাখো।

2. What is the math idea?¶

মূল idea হলো incremental update (টুকরো হিসাব হালনাগাদ)। দুটো পাশাপাশি window-র মধ্যে পার্থক্য মাত্র দুটো element — ডানে নতুন একটা ঢোকে, বাঁয়ে পুরোনো একটা বেরোয়। তাই:

নতুন sum = পুরোনো sum + (যেটা ঢুকল) − (যেটা বেরোল)

পুরো k element আবার যোগ না করে এক বিয়োগ + এক যোগ — এটাই O(n·k)-কে O(n)-এ নামায়।

3. Which basic idea does this inherit from?¶

067 — Prefix Sum-এর কাঁধে। Prefix sum-এ আমরা একটা running total ধরে রাখি আর দরকারে অংশ বের করি। Fixed window আসলে সেই running total-এর একটা চলমান রূপ — পুরো prefix না রেখে শুধু বর্তমান window-র sum ধরে রাখি, আর সরানোর সময় দুই প্রান্তে adjust করি।

আসলে fixed-window sum prefix sum দিয়েও লেখা যায়: window_sum = prefix[r+1] − prefix[r+1−k]। তাই 085 শেখায় — prefix-এর "running total" idea-টাই window-এর জন্ম দেয়, শুধু O(1) space-এ।

4. Real-life analogy¶

ভাবো একটা চলন্ত ট্রেনের ঠিক k টা বগি তুমি জানালা দিয়ে দেখছ। ট্রেন এক বগি এগোলে — সামনের একটা নতুন বগি দৃশ্যে ঢোকে, পেছনের একটা বেরিয়ে যায়। মাঝের k−2 টা বগি একই থাকে।

এখন যদি প্রতিটা বগির ওজন যোগ করতে চাও, তুমি কি প্রতিবার সব k বগি আবার গুনবে? না — আগের যোগফল থেকে যেটা বেরোল তার ওজন বাদ দাও, যেটা ঢুকল তার ওজন যোগ করো। এক বিয়োগ, এক যোগ — ব্যস। এটাই sliding window-র মিতব্যয়িতা।

5. Visual explanation¶

a = [2, 1, 5, 1, 3, 2], k = 3 — জানালা ডানে হাঁটছে:

a = [ 2 , 1 , 5 , 1 , 3 , 2 ]

window 1: [ 2  1  5 ] 1   3   2     sum = 2+1+5 = 8
window 2:   2 [ 1  5  1 ] 3   2     sum = 8 + 1 - 2 = 7   (1 ঢুকল, 2 বেরোল)
window 3:   2   1 [ 5  1  3 ] 2     sum = 7 + 3 - 1 = 9   (3 ঢুকল, 1 বেরোল)
window 4:   2   1   5 [ 1  3  2 ]   sum = 9 + 2 - 5 = 6   (2 ঢুকল, 5 বেরোল)
                                    সর্বোচ্চ = 9

প্রতিবার পুরো জানালা গুনিনি — শুধু দুই প্রান্তে adjust:

[#####] . . .            পুরোনো sum
  [#####] . .            +নতুন(ডান)  −পুরোনো(বাঁ)
    [#####] .            আবার +নতুন  −পুরোনো

6. Example input and output¶

a                      k   ->  max window sum   (কোন window)
-----------------------------------------------------------
[2, 1, 5, 1, 3, 2]     3   ->  9                [5, 1, 3]
[1, 2, 3, 4, 5]        2   ->  9                [4, 5]
[5, 5, 5]              3   ->  15               পুরোটাই
[2, 3]                 2   ->  5                [2, 3]
[-1, -2, -3, -4]       2   ->  -3               [-1, -2]
[4]                    1   ->  4                [4]

Edge case: k == len(a) হলে একটাই window (পুরো array); negative থাকলেও কাজ করে (sum যেমন তেমন)।

7. Brute force thinking¶

সরল পথ — প্রতিটা window আলাদা করে পুরো যোগ করা:

def max_window_sum_brute(a, k):
    n = len(a)
    best = None
    for start in range(n - k + 1):
        s = sum(a[start:start + k])      # প্রতিবার নতুন করে k টা যোগ
        if best is None or s > best:
            best = s
    return best

ঠিক উত্তর দেয় — প্রতিটা window-র sum স্বাধীনভাবে গুনে সর্বোচ্চটা রাখে।

8. Why brute force may be slow¶

window সংখ্যা প্রায় n − k, প্রতিটার জন্য k বার যোগ → মোট প্রায় n·k operation। n = 100000, k = 50000 হলে প্রায় ৫০০ কোটি — Time Limit Exceeded।

n = 100000, k = 50000:
  brute force   : ~5,000,000,000 যোগ     (O(n·k))
  sliding window: ~100000 step            (O(n))

মূল অপচয়: পাশাপাশি দুই window-র মাঝে শুধু দুটো element বদলায়, তবু brute force প্রতিবার সব k টা আবার যোগ করছে — একই কাজ বারবার।

9. Better thinking¶

মূল insight: পাশের window-এ যাওয়া মানে এক বিয়োগ + এক যোগ — পুরোটা আবার গুনতে হয় না।

প্রথম window-র sum একবার গোনো: s = sum(a[0:k])
তারপর প্রতি ঘর ডানে সরায়:
    s += a[r] - a[r - k]     # নতুনটা যোগ, k ঘর আগেরটা বিয়োগ
    best = max(best, s)

এক pass-এ সব window-র sum পাওয়া যায়, প্রতিটা O(1) update।

10. Thinking tweak¶

আসল "আহা!": window সরানো = নতুনটা যোগ করো, যেটা পড়ে গেল সেটা বিয়োগ করো — মাঝেরগুলো ছোঁয়ারই দরকার নেই।

মূল কাজ একটাই লাইন: s += a[r] - a[r-k]। এই এক লাইনই O(n·k)-কে O(n)-এ নামায়। আর এই "একটা ঢোকে, একটা বেরোয়" idea-ই variable window-র (086, 087) দিকে দরজা খোলে।

11. Step-by-step dry run¶

a = [2, 1, 5, 1, 3, 2], k = 3। প্রথমে s = sum(a[0:3]) = 8, best = 8:

r	a[r] (ঢোকে)	a[r-k] (বেরোয়)	s = s + ঢোকে − বেরোয়	best
(শুরু)	—	—	2+1+5 = 8	8
3	a[3]=1	a[0]=2	8 + 1 − 2 = 7	8
4	a[4]=3	a[1]=1	7 + 3 − 1 = 9	9
5	a[5]=2	a[2]=5	9 + 2 − 5 = 6	9

সর্বোচ্চ 9 ([5, 1, 3])। লক্ষ করো প্রতি step-এ মাত্র একটা যোগ + একটা বিয়োগ — মাঝের element কখনো আবার গোনা হয়নি।

12. Python solution¶

def max_window_sum(a, k):
    """ঠিক k দৈর্ঘ্যের window-গুলোর সর্বোচ্চ sum ফেরত দেয় (1 <= k <= len(a))।"""
    s = sum(a[:k])
    best = s
    for r in range(k, len(a)):
        s += a[r] - a[r - k]          # নতুনটা যোগ, পুরোনোটা বিয়োগ
        if s > best:
            best = s
    return best


def window_sums(a, k):
    """প্রতিটা window-র sum-এর list (পরপর) ফেরত দেয় — দেখার জন্য।"""
    s = sum(a[:k])
    out = [s]
    for r in range(k, len(a)):
        s += a[r] - a[r - k]
        out.append(s)
    return out


def max_window_sum_brute(a, k):
    """ধীর reference — প্রতিটা window নতুন করে যোগ।"""
    n = len(a)
    best = None
    for start in range(n - k + 1):
        s = sum(a[start:start + k])
        if best is None or s > best:
            best = s
    return best


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert max_window_sum([2, 1, 5, 1, 3, 2], 3) == 9
assert max_window_sum([1, 2, 3, 4, 5], 2) == 9
assert max_window_sum([5, 5, 5], 3) == 15
assert max_window_sum([2, 3], 2) == 5
assert max_window_sum([-1, -2, -3, -4], 2) == -3
assert max_window_sum([4], 1) == 4
assert window_sums([2, 1, 5, 1, 3, 2], 3) == [8, 7, 9, 6]

# brute force-এর সাথে মিলিয়ে দেখা (নানা random case)
import random
random.seed(17)
for _ in range(400):
    n = random.randint(1, 12)
    arr = [random.randint(-5, 5) for _ in range(n)]
    k = random.randint(1, n)
    assert max_window_sum(arr, k) == max_window_sum_brute(arr, k), (arr, k)

print(max_window_sum([2, 1, 5, 1, 3, 2], 3))   # 9
print(window_sums([2, 1, 5, 1, 3, 2], 3))      # [8, 7, 9, 6]
print(max_window_sum([1, 2, 3, 4, 5], 2))      # 9
print("সব test pass!")

13. Line-by-line explanation¶

s = sum(a[:k])
best = s

প্রথম window-র sum একবারই পুরো গোনা হয়; সেটাই শুরুর সেরা।

for r in range(k, len(a)):

r হলো নতুন ঢোকা element-এর index; শুরু k থেকে কারণ প্রথম window [0..k-1] আগেই গোনা।

    s += a[r] - a[r - k]

হৃদয় — নতুন a[r] যোগ, ঠিক k ঘর আগের a[r-k] (যেটা window থেকে পড়ে গেল) বিয়োগ।

    if s > best: best = s

প্রতি window-র পর সেরাটা হালনাগাদ।

window_sums সব window-র sum দেখায়; max_window_sum_brute test যাচাইয়ের reference (random case-এ মিলিয়ে দেখা)।

14. Output walkthrough¶

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

9
[8, 7, 9, 6]
9
সব test pass!

প্রথম লাইন সর্বোচ্চ window sum 9; দ্বিতীয় লাইন প্রতিটা window-র sum পরপর [8, 7, 9, 6]; তৃতীয় লাইন [1..5] k=2-এর সর্বোচ্চ 9 ([4,5])। তার আগে 400 random case brute-force-এর সাথে মিলেছে, তাই সব test pass!।

15. Time complexity¶

O(n) — প্রথম window O(k) একবার, এরপর প্রতিটা slide O(1) (এক যোগ + এক বিয়োগ), মোট প্রায় n বার। তাই O(k + n) = O(n)।

16. Space complexity¶

O(1) — শুধু s, best (max চাইলে)। (সব window-র sum list চাইলে O(n), কিন্তু শুধু সর্বোচ্চের জন্য বাড়তি জায়গা প্রায় শূন্য।)

17. Common mistakes¶

প্রতি window পুরো আবার যোগ করা — তখন O(n·k); incremental update-ই আসল লাভ।
a[r - k] বিয়োগ ভুলে যাওয়া — শুধু যোগ করলে window বড় হতে থাকে, sum ভুল।
প্রথম window ভুলে loop শুরু করা — range(k, ...) থেকে শুরু; প্রথম [0..k-1] আগে আলাদা করে গুনতে হয়।
k > len(a) না ভাবা — তখন window-ই হয় না; বাস্তবে 1 <= k <= len(a) ধরে নেওয়া বা আগে যাচাই।
negative element ভয় পাওয়া — fixed window negative-এও দিব্যি চলে (sum যেমনই হোক); ভয়টা variable window-এ (086+)।

18. Harder problems that inherit this idea¶

GeeksforGeeks Window Sliding Technique (https://www.geeksforgeeks.org/window-sliding-technique/) — fixed-window-এর মূল ব্যাখ্যা ও অনুশীলন।
LeetCode Maximum Average Subarray I (https://leetcode.com/problems/maximum-average-subarray-i/) — হুবহু fixed window, শুধু sum-কে গড় বানানো।
LeetCode Sliding Window Maximum (https://leetcode.com/problems/sliding-window-maximum/) — fixed window + monotonic deque, পরের ধাপ।

19. Pattern learned¶

Fixed-size sliding window with incremental update — s += a[r] - a[r-k]; পুরো window কখনো আবার গোনা না। বড় শিক্ষা: পাশাপাশি দুই window-র পার্থক্য মাত্র দুই element — তাই hisaব হালনাগাদ করো, নতুন করে গোনো না।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "fixed window = প্রথমটা একবার গোনো, তারপর প্রতি ঘরে s += a[r] − a[r−k]; O(n·k) থেকে O(n)। Signal: 'ঠিক k দৈর্ঘ্যের subarray-র উপর কিছু' দেখলেই fixed window + incremental update মনে পড়ুক।"

পরের ধাপ → 086 — Longest Subarray with Sum K (Positive) (এবার window-র দৈর্ঘ্য নিজেই বদলাবে)। ভিত্তি → ../../05-prefix-difference-contribution/problems/067-prefix-sum.md।

ফিরে দেখা: এই 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" লেখো।