016 — Sliding Window Maximum (heap variant)¶

Source¶

Original source: Classic sliding-window maximum via a max-heap with lazy deletion
Platform: LeetCode — https://leetcode.com/problems/sliding-window-maximum/
Topic: heap / priority queue
Difficulty: Hard
Pattern: Lazy deletion (stale entry top-এ এলে তবেই purge)
Basic idea inherited from: 04-stack-and-queue monotonic deque — সেই idea-র সহজ-মনে-রাখা heap রূপ

1. Problem in simple words¶

একটা array nums আর একটা window size k দেওয়া। একটা size-k-এর window বাঁদিক থেকে ডানদিকে এক ঘর করে slide করে। প্রতিটা window position-এ সেই window-এর সবচেয়ে বড় element-টা চাই। সব window-এর maximum গুলো order-এ একটা list-এ return করো। মোট window সংখ্যা len(nums) - k + 1।

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3  ->  [3, 3, 5, 5, 6, 7]

2. Which basic idea does this inherit from?¶

ভিত 04-stack-and-queue-এর monotonic deque, যেটা এই problem O(n)-এ solve করে। কিন্তু deque-এর invariant মনে রাখা একটু কসরত; heap version হলো সেই idea-র সহজ-মনে-রাখা, general রূপ — সাথে 08-এর lazy deletion trick, কারণ heap মাঝখান থেকে সস্তায় delete করতে পারে না।

3. What is the hidden math or logic?¶

লুকানো logic: heap থেকে arbitrary element delete করা ব্যয়বহুল, তাই delete-ই করো না। প্রতিটা element-কে (value, index) হিসেবে রাখো। Window সরালে কিছু element "stale" হয়ে যায় (index window-এর বাইরে)। তাদের সাথে সাথে মোছা লাগে না — শুধু যখন তারা heap-এর top-এ ভেসে ওঠে আর আমরা max পড়তে চাই, তখনই purge করো। প্রতিটা element একবার ঢোকে আর বড়জোর একবার বেরোয়।

4. Which data structure is needed?¶

একটা max-heap of (value, index)। heapq min-heap বলে value negate করি — সবচেয়ে negative মানে সবচেয়ে বড় value। index রাখি যাতে top window-এর ভেতরে আছে কিনা চেক করা যায়।

5. Why this data structure fits¶

প্রতিটা window-এ দরকার শুধু max — পুরো sorted order না। Heap top O(1)-সম max দেয়, push O(log n)। Window সরার সাথে যে element-রা বাইরে গেছে তাদের সাথে সাথে খুঁজে মুছতে গেলে heap-এ O(n); তাই lazy deletion — top-এ stale element এলে তবেই pop। মোট কাজ O(n log n)।

6. Real-life analogy¶

ভাবো একটা পার্টিতে guest list থেকে কারও নাম কাটতে হলে তুমি ভিড়ের মধ্যে গিয়ে তাকে খুঁজে বের করো না — শুধু list-এ নামটা কেটে রাখো। দরজার bouncer (তোমার pop loop) তখনই list দেখে যখন কেউ "সবার আগের লোক" হিসেবে দরজায় পৌঁছায়; নাম কাটা থাকলে তাকে ঢুকতে না দিয়ে সরিয়ে দেয়। সেই "সবার আগের লোক চট করে দাও, stale হলে সরাও" যন্ত্রটাই lazy-deletion heap।

7. Visual explanation¶

nums = [1,3,-1,-3,5,3], k = 3 — max-heap-এ (-value, index); top window-এর বাইরে হলে purge, তারপর max পড়ি:

i=0: push(-1,0)                          window not full
i=1: push(-3,1)                          window not full
i=2: push(-(-1),2)                       top=(-3,1)=val3,idx1 in [0..2] -> max 3
i=3: push(-(-3),3)                       top=val3,idx1 in [1..3] -> max 3
i=4: push(-5,4)                          top=(-5,4)=val5 in [2..4] -> max 5
i=5: push(-3,5)                          top=val5,idx4 in [3..5] -> max 5

answers: [3, 3, 5, 5]

8. Example input and output¶

Input : nums=[1,3,-1,-3,5,3,6,7], k=3  -> Output: [3, 3, 5, 5, 6, 7]
Input : nums=[1], k=1                   -> Output: [1]
Input : nums=[9,8,7,6], k=2             -> Output: [9, 8, 7]   (descending)
Input : nums=[4,4,4,4], k=2             -> Output: [4, 4, 4]   (সব সমান)

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা window position-এ সেই k-টা element-এর উপর max() চালাও।

[1,3,-1] -> max 3 ; [3,-1,-3] -> max 3 ; [-1,-3,5] -> max 5 ; ...

10. Why brute force is slow¶

প্রতিটা window-এ k element-এর max মানে window-প্রতি O(k), window সংখ্যা O(n) — মোট O(n·k)। k বড় হলে এটা প্রায় O(n²)। অথচ পাশাপাশি window-গুলো প্রায় পুরোটাই overlap করে; প্রতিবার শূন্য থেকে max বের করা অপচয়।

11. Key observation¶

মূল observation: একটা element একবার heap-এ ঢুকলে আর কখনো নতুন করে ঢোকে না; সে শুধু stale হয়ে top-এ এলে একবার বেরোয়। তাই push/pop মোট O(n)-বার, প্রতিটা O(log n)। "stale top purge" করা ছাড়া আর কোনো deletion লাগে না — heap-এর "শুধু top দেখা যায়" সীমাকেই feature বানানো হলো।

12. Optimized intuition¶

প্রতিটা index i-তে (-nums[i], i) heap-এ push করো। window পূর্ণ হলে (i >= k-1): যতক্ষণ heap-এর top-এর index <= i - k (window-এর বাইরে), pop করে purge করো; তারপর top-এর negated value-ই current window-এর max — সেটা answer-এ যোগ করো। প্রতিটা element একবার push, বড়জোর একবার pop।

13. Thinking tweak¶

মোচড়: "window থেকে element সরানো" না ভেবে ভাবো "stale হয়ে গেলে কিছু করি না; শুধু যখন stale জিনিস top-এ এসে max পড়ায় বাগড়া দেয়, তখনই ঝেড়ে ফেলি।" "sliding window + heap / arbitrary delete / values expire" — এমন কথা শুনলেই lazy deletion-এর কথা মাথায় আসা উচিত।

14. Step-by-step dry run¶

Input nums=[9,8,7,6], k=2:

heap empty, out=[]
i=0: push (−9,0); window পূর্ণ নয় (i < k−1=1)
i=1: push (−8,1); window পূর্ণ; top (−9,0), idx 0 ≤ i−k = −1? না (0 > −1) → in window; max = 9 → out [9]
i=2: push (−7,2); top (−9,0), idx 0 ≤ i−k = 0? হ্যাঁ → pop (stale); top এখন (−8,1), idx 1 ≤ 0? না → max 8 → out [9,8]
i=3: push (−6,3); top (−8,1), idx 1 ≤ i−k = 1? হ্যাঁ → pop; top (−7,2), idx 2 ≤ 1? না → max 7 → out [9,8,7]
return [9, 8, 7]

15. Python solution¶

import heapq

def max_sliding_window(nums, k):
    heap = []                       # (-value, index) — max-heap via negation
    out = []
    for i, x in enumerate(nums):
        heapq.heappush(heap, (-x, i))
        if i >= k - 1:              # window পূর্ণ হলেই উত্তর লেখা শুরু
            # top যদি window-এর বাইরে হয় (stale), লেজি ভাবে purge করো
            while heap[0][1] <= i - k:
                heapq.heappop(heap)
            out.append(-heap[0][0])     # বর্তমান window-এর max
    return out

# ---- tests ----
assert max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]
assert max_sliding_window([1], 1) == [1]                 # একটাই element
assert max_sliding_window([9, 8, 7, 6], 2) == [9, 8, 7]  # descending
assert max_sliding_window([4, 4, 4, 4], 2) == [4, 4, 4]  # সব সমান
assert max_sliding_window([-7, -8, 7, 5, 7, 1, 6, 0], 4) == [7, 7, 7, 7, 7]

print("সব test pass!")

16. Line-by-line code explanation¶

heap = [] — (-value, index)-এর max-heap; negation-এ heapq-কে max দেয়ার মতো বানায়।
for i, x in enumerate(nums): — প্রতিটা element তার index সহ।
heapq.heappush(heap, (-x, i)) — প্রতিটা element একবারই heap-এ ঢোকে।
if i >= k - 1: — প্রথম পূর্ণ window তৈরি হলে তবেই উত্তর লেখা শুরু।
while heap[0][1] <= i - k: heappop(heap) — top-এর index window-এর বাইরে হলে (stale) ঝেড়ে ফেলো; ভেতরের কিছু থাকতে থাকতে থামো।
out.append(-heap[0][0]) — এখন top window-এর ভেতরে আর সবচেয়ে বড়; negate করে আসল max।

17. Output walkthrough¶

max_sliding_window([9,8,7,6], 2) section 14-এর dry run মেনে [9,8,7] দেয় — assert pass। main example [3,3,5,5,6,7]; single [1] k=1 → [1]; সব-সমান [4,4,4,4] → [4,4,4]; negative-mix-এও সঠিক max ধরা পড়ে। প্রতিটা window-এর max একটা নির্দিষ্ট sequence, তাই সরাসরি সমতা assert। সব pass-এর পরে print হয়: সব test pass!।

18. Time complexity¶

O(n log n) — প্রতিটা element একবার push আর বড়জোর একবার pop হয় (প্রতিটা O(log n))। কোনো কোনো window-তে একসাথে কয়েকটা stale top purge হলেও amortized মোট pop সংখ্যা O(n)। (monotonic deque এটা O(n)-এ করে; heap version মনে রাখা সহজ।)

19. Space complexity¶

O(n) — worst case (যেমন strictly increasing array) heap-এ প্রায় সব element একসাথে stale-সহ জমে থাকতে পারে। Deque version O(k)-তে রাখে; এটা সরলতার বদলে একটু বেশি memory নেয়।

20. Common mistakes¶

max-heap না বানিয়ে সরাসরি heapq ব্যবহার — তখন তুমি min track করছ, ভুল উত্তর।
purge করার সময় ভুল bound (< i - k বনাম <= i - k) — off-by-one; window-এর ঠিক বাইরের index i - k, তাই <=।
window পূর্ণ হওয়ার আগেই answer লেখা শুরু — প্রথম k-1 index-এ কিছু append করা ভুল।
purge-এর পর top না পড়ে আগের top পড়া — purge-loop শেষে heap[0]-ই current max।

21. Which basic problem this inherits from¶

ভিত্তি 04-stack-and-queue-এর monotonic deque (একই problem-এর O(n) সমাধান) আর 08-এর patterns.md-র Pattern 5 (Lazy deletion) — "stale entry heap-এ থাকতে দাও, top-এ এলে purge"। heap-এর "শুধু top দেখা যায়" সীমাকে এখানে কাজে লাগানো হলো।

22. Similar harder problems¶

Sliding Window Median — https://leetcode.com/problems/sliding-window-median/ (এই tracker-এর #21; two heaps + lazy deletion)
Find Median from Data Stream — https://leetcode.com/problems/find-median-from-data-stream/ (#18; two heaps)
Shortest Subarray with Sum at Least K — https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/ (monotonic deque-এর আরেক প্রয়োগ)

23. Pattern learned¶

Lazy deletion: heap মাঝখান থেকে সস্তায় delete করতে পারে না, তাই deletion অন্য কোথাও লিখে রাখো (এখানে index vs window bound) আর stale top-গুলো শুধু peek/pop-এর সময় purge করো। "heap থেকে arbitrary element সরাও" দরকার পড়লেই এই trick মনে করো।

24. Final summary¶

ভবিষ্যতের আমাকে: "sliding window-এর max, heap দিয়ে" = (-value, index) max-heap, window পূর্ণ হলে top-এর index window-এর বাইরে থাকলে purge, তারপর top-ই max। Deque O(n)-এ করে, কিন্তু এই lazy-deletion heap মনে রাখা সহজ আর Sliding Window Median-এর সরাসরি প্রস্তুতি।

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