কনটেন্টে যান

021 — Sliding Window Median

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

  • Original source: Running median over a fixed-size window (two heaps + lazy deletion)
  • Platform: LeetCode — https://leetcode.com/problems/sliding-window-median/
  • Topic: heap / priority queue
  • Difficulty: Hard
  • Pattern: Two heaps (lower max-heap + upper min-heap) + lazy deletion + rebalancing
  • Basic idea inherited from: 08 two heaps + lazy deletion — 018-এর running median + window-এর জন্য element সরানো

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

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

একটা array nums আর একটা window-আকার k দেওয়া। window বাঁ থেকে ডানে এক ঘর করে সরছে। প্রতিটা position-এ window-এর ভেতরের k-টা সংখ্যার median বের করতে হবে। k বিজোড় হলে median = মাঝেরটা; জোড় হলে মাঝের দুটোর গড়। সব position-এর median গুলো একটা list-এ ফেরত দাও।

উদাহরণ
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
window গুলোর median -> [1, -1, -1, 3, 5, 6]

Input ও output

উদাহরণ
Input : nums=[1,3,-1,-3,5,3,6,7], k=3   -> Output: [1, -1, -1, 3, 5, 6]
Input : nums=[1,2,3,4], k=2             -> Output: [1.5, 2.5, 3.5]
Input : nums=[5], k=1                   -> Output: [5.0]
Input : nums=[1,4,2,3], k=4             -> Output: [2.5]   (পুরোটাই একটা window)

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

ভাবো একটা চলন্ত দাঁড়িপাল্লা (seesaw)। বাঁ পাল্লায় ছোট সংখ্যা, ডান পাল্লায় বড় — median মাঝখানে। window সরলে ডান দিক থেকে নতুন এক জন উঠছে, বাঁ দিক থেকে এক জন নামছে। কিন্তু পাল্লার মাঝখান থেকে কাউকে টেনে নামানো ঝামেলা — তাই তাকে শুধু "চলে যাওয়ার তালিকা"-য় টিক দাও; কিনারায় চলে এলে তবেই সত্যিকারে নামাও। পাল্লা দুটো প্রায় সমান ভারী রাখো — মাঝখানের value(s), মানে median, সবসময় হাতের নাগালে।

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

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

ভিত 08-এর two heaps (018 Find Median from Data Stream-এর মতো — lower half max-heap, upper half min-heap, balanced) আর তার ওপর নতুন একটা চাল: lazy deletion। stream-এ শুধু যোগ হতো; window-এ একটা পুরোনো element প্রতি step-এ বেরিয়েও যায়। heap-এর মাঝখান থেকে সরাসরি মোছা যায় না, তাই সেটাকে "মুছে ফেলা" বলে চিহ্নিত রেখে, top-এ এলে তবে সত্যিকারে ঝেড়ে ফেলা — এটাই lazy deletion (016 Sliding Window Maximum-এও দেখেছ)।

ভেতরের যুক্তি

লুকানো logic দুই ভাগে। (১) median = balanced দুই অর্ধের কিনারা — ছোট অর্ধের max আর বড় অর্ধের min, যেমন 018-এ। (২) Window সরলে একটা পুরোনো value বাদ দিতে হয়, কিন্তু heap mid থেকে মোছা O(n)। তাই একটা hash-map-এ "কোন value কতবার মুছতে হবে" গুনে রাখি, আর শুধু top যখন এমন একটা মুছে-ফেলা-value হয় তখনই pop করি। সাথে দুই heap-এর effective size balance ধরে রাখি, যাতে top গুলো সত্যিই median ছোঁয়।

কী দিয়ে তথ্য রাখব

দুটো heap + একটা hash-map (counter)। (1) lower — ছোট অর্ধের max-heap (negate করা)। (2) upper — বড় অর্ধের min-heap। (3) to_delete — value → কতবার lazily মুছতে হবে, এর dict। সাথে দুটো counter (low_size, up_size) — heap-এ এখনো valid (না-মোছা) কতগুলো element আছে।

এটি কেন উপযুক্ত

Median পেতে শুধু দুই অর্ধের boundary লাগে। Heap balance করা এবং stale top সরানোর পরে এই boundary থেকে O(1)-এ median পড়া যায়। Window সরলে নতুন value push হয়, আর পুরোনো value মুছে দেওয়ার জন্য mark করা হয়। এই implementation-এ heap-এর নিচে stale entry জমতে পারে, তাই physical heap size সবসময় k নয়। Worst-case মোট সময় O(n log n); প্রতিটি window নতুন করে sort করতে হয় না।

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

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

প্রথম সরল চিন্তা: প্রতিটা window-এর জন্য তার k-টা element আলাদা করে নাও, sort করো, মাঝের element (বা দুটোর গড়) median হিসেবে নাও। window এক ঘর সরলেই আবার পুরো sort।

উদাহরণ
প্রতি window: slice নাও -> sort -> মাঝখান নাও
   n-k+1 টা window x প্রতিটায় O(k log k) sort

কোথায় বেশি কাজ হচ্ছে

প্রতি window-এ পুরো k element sort মানে O(k log k); window সংখ্যা প্রায় n — মোট O(n·k log k), বড় input-এ ভারী। অথচ পরপর দুটো window-এ মাত্র একটা element বদলায় (একটা ঢোকে, একটা বের হয়)। পুরো জিনিস আবার sort করা সেই overlap-টা পুরো নষ্ট করা।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: পরপর দুটো window প্রায় পুরোটাই এক — শুধু এক প্রান্তে একটা নতুন value, অন্য প্রান্তে একটা পুরোনো বাদ। তাই পুরো structure আবার বানানোর দরকার নেই; দুই balanced heap-এ একটা insert + একটা delete করলেই median update হয়ে যায়। আর mid থেকে delete-টা lazy করলে heap-এর সস্তা property নষ্ট হয় না।

আরও কম কাজে সমাধান

দুই heap-এ প্রথম window ভরুন এবং valid size দিয়ে balance রাখুন। প্রতি slide-এ পুরোনো value-কে to_delete-এ mark করে তার অর্ধের valid size কমান, নতুন value insert করুন, balance ঠিক করুন এবং stale top সরান। k বিজোড় হলে lower-এর top, জোড় হলে দুই top-এর গড় নিন। নিচের code নতুন value যোগ করার পরে পূর্ণ window-এর median নেয় এবং পরের window-এর জন্য পুরোনো value সরায়; একই window-সীমা বজায় থাকে। Rebuild ছাড়া lazy deletion-এ মোট worst-case O(n log n)।

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

মোচড়: "window-এর median" না ভেবে ভাবো "018-এর running median, কিন্তু এবার একটা পুরোনো element প্রতি step-এ বিদায় নেয় — heap mid থেকে সরাসরি মোছা যায় না বলে lazy delete করি।" "fixed window + median/order-statistic" শুনলেই দুই heap + lazy deletion মনে করবে; এটা 018 (two heaps) আর 016 (lazy deletion)-এর মিলন।

ছবিতে বোঝা

nums = [1,3,-1,-3,5,3,6,7], k = 3 — lower max-heap, upper min-heap (effective view):

উদাহরণ
window [1,3,-1] -> sorted {-1,1,3}
   lower(max) top = 1 | upper(min) top = 3      median = 1

slide: -1 বের, -3 ঢোকে -> {-3,-1,3}? না, window [3,-1,-3]
   sorted {-3,-1,3}  -> median = -1
   (-1 কে lazy-delete চিহ্ন, top-এ এলে ঝাড়া)

slide: window [-1,-3,5] -> sorted {-3,-1,5}     median = -1
slide: window [-3,5,3]  -> sorted {-3,3,5}      median = 3
slide: window [5,3,6]   -> sorted {3,5,6}       median = 5
slide: window [3,6,7]   -> sorted {3,6,7}       median = 6

উত্তর: [1, -1, -1, 3, 5, 6]

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

Input nums = [1, 2, 3, 4], k = 2 (জোড় k, তাই median = দুই top-এর গড়):

  1. প্রথম window [1, 2]: insert 1, insert 2, balance → lower top 1, upper top 2; median = (1+2)/2 = 1.5
  2. slide → window [2, 3]: পুরোনো 1 বাদ (lazy mark, lower-এ ছিল); নতুন 3 insert; balance; top-গুলো থেকে lazy-deleted ঝাড়া → lower top 2, upper top 3; median = (2+3)/2 = 2.5
  3. slide → window [3, 4]: পুরোনো 2 বাদ (lazy mark); নতুন 4 insert; balance; ঝাড়া → lower top 3, upper top 4; median = (3+4)/2 = 3.5
  4. আর slide নেই → return [1.5, 2.5, 3.5]

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

Python

Python
import heapq

def median_sliding_window(nums, k):
    # lower = ছোট অর্ধের max-heap (negate করা), upper = বড় অর্ধের min-heap
    lower, upper = [], []
    to_delete = {}              # lazily-মোছা value -> কতবার মুছতে বাকি
    low_size = up_size = 0      # দুই অর্ধে এখনো valid (না-মোছা) কতগুলো

    def prune(heap):           # top যতক্ষণ মৃত (delete বাকি) ততক্ষণ সত্যিকারে ঝাড়ো
        while heap:
            val = -heap[0] if heap is lower else heap[0]
            if to_delete.get(val, 0) > 0:
                to_delete[val] -= 1
                heapq.heappop(heap)
            else:
                break

    def balance():             # invariant: valid lower size == upper size বা +1
        nonlocal low_size, up_size
        if low_size > up_size + 1:        # lower-এ বেশি -> একটা upper-এ পাঠাও
            prune(lower)
            heapq.heappush(upper, -heapq.heappop(lower))
            low_size -= 1; up_size += 1
        elif low_size < up_size:          # upper-এ বেশি -> একটা lower-এ আনো
            prune(upper)
            heapq.heappush(lower, -heapq.heappop(upper))
            up_size -= 1; low_size += 1
        prune(lower); prune(upper)        # দুই top পরিষ্কার রাখো

    def add(x):
        nonlocal low_size, up_size
        if not lower or x <= -lower[0]:   # ছোট অর্ধে যাবে
            heapq.heappush(lower, -x); low_size += 1
        else:                             # বড় অর্ধে যাবে
            heapq.heappush(upper, x); up_size += 1
        balance()

    def remove(x):
        nonlocal low_size, up_size
        to_delete[x] = to_delete.get(x, 0) + 1     # lazy mark
        # যে অর্ধে value-টা logically আছে, সেই অর্ধের size কমাও; top হলে এখনই
        # prune করো যাতে delete-credit ঠিক জায়গায় খরচ হয় (duplicate-safe)।
        if lower and x <= -lower[0]:      # lower-অর্ধে ছিল
            low_size -= 1
            prune(lower)
        else:                             # upper-অর্ধে ছিল
            up_size -= 1
            prune(upper)
        balance()

    def median():
        if k % 2 == 1:
            return float(-lower[0])                 # বিজোড়: lower-এর top
        return (-lower[0] + upper[0]) / 2.0         # জোড়: দুই top-এর গড়

    result = []
    for i, x in enumerate(nums):
        add(x)
        if i >= k - 1:                    # window পূর্ণ
            result.append(median())
            remove(nums[i - k + 1])       # সবচেয়ে পুরোনো element বিদায়
    return result

# ---- tests ----
assert median_sliding_window([1,3,-1,-3,5,3,6,7], 3) == [1, -1, -1, 3, 5, 6]
assert median_sliding_window([1,2,3,4], 2) == [1.5, 2.5, 3.5]
assert median_sliding_window([5], 1) == [5.0]
assert median_sliding_window([1,4,2,3], 4) == [2.5]      # পুরোটাই এক window
assert median_sliding_window([7,7,7], 2) == [7.0, 7.0]   # duplicate
print("সব test pass!")

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

  • lower, upper = [], [] — ছোট অর্ধের max-heap (negate করা) আর বড় অর্ধের min-heap; median এদের top-এ।
  • low_size, up_size — দুই অর্ধে এখনো valid (lazy-মোছা বাদ) কতগুলো element, balance ঠিক রাখতে।
  • prune(heap) — top যতক্ষণ এমন value যার delete বাকি আছে, ততক্ষণ pop করে সত্যিকারে ঝেড়ে ফেলি।
  • balance() — invariant ধরে রাখে: valid lower size সমান বা একটা বেশি; দরকারমতো একটা element এক heap থেকে অন্যটায় সরায়; শেষে দুই top prune করে পরিষ্কার রাখে।
  • add(x) — নতুন value top-এর সাথে তুলনা করে ঠিক অর্ধে push, size বাড়াই, তারপর balance()।
  • remove(x) — value-কে to_delete-এ গুনে রাখি (lazy mark); সে কোন অর্ধে ছিল বুঝে valid size কমাই, আর top হলে সেই অর্ধেই এখনই prune করি (যাতে duplicate value-এর delete-credit ঠিক heap-এ খরচ হয়), তারপর balance()।
  • median() — k বিজোড় → lower-এর top; জোড় → দুই top-এর গড় (float)।
  • মূল loop — প্রতিটা element add করি; window পূর্ণ হলে median নিই, তারপর সবচেয়ে পুরোনো element remove করি।

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

median_sliding_window([1,2,3,4], 2) section 14-এর dry run মেনে [1.5, 2.5, 3.5] দেয় — assert pass। প্রথম example-এ প্রতিটা window-এর সরানো median মিলে [1, -1, -1, 3, 5, 6]। [5], k=1 → একটাই window, median 5.0। [1,4,2,3], k=4 → পুরোটা sorted {1,2,3,4}, মাঝের (2+3)/2 = 2.5। [7,7,7], k=2 → duplicate ঠিকঠাক lazy-delete হয়ে [7.0, 7.0]। median নির্দিষ্ট value, তাই সরাসরি সমতা assert। সব pass-এর পরে print হয়: সব test pass!।

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

সময়

O(n log n) worst case, এই implementation-এর জন্য। মোট add, rebalance এবং stale-pop operation O(n), কিন্তু physical heap-এ stale entry-সহ O(n) item থাকতে পারে। তাই heap operation-এর bound O(log n)। Top পরিষ্কার ও balance ঠিক থাকলে median পড়া O(1)। Heap-এর আকার O(k)-তে রাখতে periodic rebuild বা সরাসরি deletion সমর্থনকারী structure যোগ করলে O(n log k) অর্জন করা যায়; এখানে সে ব্যবস্থা নেই।

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

O(n) worst-case auxiliary space। Valid element বড়জোর kটি হলেও stale entry ও deletion map বড় হতে পারে। যেমন increasing input-এ পুরোনো ছোট value lower max-heap-এর নিচে থেকে যায়, top-এ আসে না বলে সঙ্গে সঙ্গে মুছে যায় না। Output list আলাদাভাবে O(n−k+1)।

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

  • lower-কে max-heap না বানিয়ে সরাসরি heapq — তখন partition উল্টে median ভুল।
  • valid size আলাদা করে না গোনা, শুধু len(heap) দিয়ে balance — lazy-deleted entry গুলো গণনায় ঢুকে balance ভেঙে দেয়।
  • কোন অর্ধ থেকে element বাদ যাচ্ছে ভুল বোঝা — remove-এর সময় value-কে -lower[0]-এর সাথে তুলনা করে ঠিক অর্ধ নির্ণয় করা জরুরি।
  • জোড় k-তে integer division (//) ব্যবহার — median float হতে পারে (যেমন 1.5), তাই / আর 2.0।
  • prune করতে ভুলে যাওয়া — top-এ মৃত value পড়ে থাকলে median বা balance ভুল হয়।
  • duplicate value-এর ফাঁদ: একই value যদি দুই heap-এ থাকে, to_delete heap-নিরপেক্ষ — তাই remove-এ যে অর্ধের size কমালে, সেই অর্ধেই সঙ্গে সঙ্গে prune না করলে credit ভুল heap-এ খরচ হয়ে size desync হয় (খালি heap-এ pop → IndexError)।

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

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি 08-এর patterns.md-র Pattern 3 (Two heaps for running median — 018 MedianFinder-এর মতো lower max + upper min) আর Pattern 5/lazy-deletion idea (016 Sliding Window Maximum-এ heap top থেকে stale entry ঝাড়া)। এই দুই pattern একসাথে জুড়লেই sliding window median।

পরের অনুশীলন

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

Two heaps + lazy deletion: balanced দুই heap (lower max + upper min) দিয়ে median ধরে রাখো; window সরলে একটা insert + একটা delete করো, কিন্তু mid থেকে delete-টা "মার্ক করে রাখো, top-এ এলে ঝাড়ো" — lazy। valid size আলাদা গুনে balance রাখো। "fixed window + median/order statistic" পেলেই এই combo।

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

ভবিষ্যতের আমাকে: sliding window median = 018-এর দুই heap + lazy deletion। প্রতি slide-এ নতুন element add, পুরোনো element-কে to_delete-এ মার্ক করে valid size কমাও, balance ঠিক করো, top থেকে মৃত value ঝাড়ো, তারপর median পড়ো। মনে রেখো — heap mid থেকে সরাসরি মোছা যায় না, তাই lazy; আর balance-এর হিসাব valid (না-মোছা) size দিয়ে করো, raw length দিয়ে নয়।

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