019 — Sliding Window Maximum¶

Problem link ও উৎস

Original source: Classic monotonic-deque exercise (chapter centerpiece)
Platform: LeetCode — https://leetcode.com/problems/sliding-window-maximum/
Topic: queue (monotonic deque)
Difficulty: Hard
Pattern: monotonic deque
Basic idea inherited from: sliding window basic (../../02-arrays-and-strings/) + queue — full walkthrough ../patterns.md Pattern 5-এ

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

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

তোমাকে একটা সংখ্যার array nums আর একটা window size k দেওয়া আছে। একটা k-চওড়া জানালা বাঁ প্রান্ত থেকে ডান প্রান্তে এক ঘর করে slide করো; প্রতিটা অবস্থানে জানালার ভেতরের k-টা সংখ্যার maximum report করো। শেষে এই maximum গুলোর list ফেরত দাও।

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3-এর জন্য:

উদাহরণ

window                 max
[1  3 -1]-3  5 3 6 7    3
 1 [3 -1 -3] 5 3 6 7    3
 1  3[-1 -3  5]3 6 7    5
 1  3 -1[-3  5 3]6 7    5
 1  3 -1 -3 [5 3 6]7    6
 1  3 -1 -3  5[3 6 7]   7
answer = [3, 3, 5, 5, 6, 7]

Input ও output¶

উদাহরণ

Input : nums=[1,3,-1,-3,5,3,6,7], k=3 -> [3, 3, 5, 5, 6, 7]
Input : nums=[9,8,7,6], k=2           -> [9, 8, 7]
Input : nums=[4,4,4,4], k=2           -> [4, 4, 4]

Edge case 1 (k=1)        : [1,5,2], k=1 -> [1,5,2]  (প্রতিটা element নিজেই window)
Edge case 2 (k=len)      : [1,3,-1], k=3 -> [3]     (একটাই window)
Edge case 3 (খালি)       : [], k=3       -> []

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

ভাবো deque হলো একটা "ভবিষ্যতের চ্যাম্পিয়ন হতে পারি" দের waiting room, যেখানে লোকেরা শক্তির ক্রমে দাঁড়িয়ে — সামনে সবচেয়ে শক্তিশালী। নতুন একজন শক্তিশালী লোক পেছনের দরজা দিয়ে ঢুকলে, পেছনে দাঁড়ানো যত দুর্বল লোক আছে (তার সমান বা কম শক্তির) সবাইকে সাথে সাথে বের করে দেওয়া হয় — তারা তো আর কখনো জিততে পারবে না, কারণ নতুন লোক তাদের চেয়ে শক্তিশালী আর বেশিদিন থাকবে। আর সামনের লোকের মেয়াদ (window) শেষ হলে তাকে সামনের দরজা দিয়ে বিদায়। তাই room-এর সামনের জনই সবসময় বর্তমান চ্যাম্পিয়ন।

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

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

এটা দুটো জিনিসের মিলন (../patterns.md Pattern 5)। প্রথমত sliding window basic (../../02-arrays-and-strings/) — এক ধাপ করে এগোতে থাকা একটা window। দ্বিতীয়ত queue — window-র candidate-রা এক প্রান্তে ঢোকে আর FIFO order-এ অন্য প্রান্তে expire করে। নতুন উপাদানটা হলো পেছনের প্রান্ত থেকেও eject করতে দেওয়া — এটাই queue-কে upgrade করে একটা deque (double-ended queue)-এ।

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

লুকানো logic হলো একটা dominance invariant: deque-তে আমরা শুধু সেই index গুলো রাখি যারা "ভবিষ্যতের কোনো window-র জন্য এখনো max হওয়ার দাবিদার", আর তাদের value গুলো front থেকে back পর্যন্ত strictly কমতে থাকে (monotonic decreasing)।

কেন এটা ঠিক রাখা যায়? একটা নতুন value x এলে, deque-র যেকোনো element যেটা x-এর চেয়ে ছোট-বা-সমান, সে আর কোনোদিন কোনো window-র max হতে পারবে না — কারণ x একইসাথে নতুন (তাই বেশিদিন বাঁচবে) আর বড়-বা-সমান (তাই হারাবে না)। তাই তাদের পেছন থেকে ফেলে দেওয়া নিরাপদ। ফলে deque সবসময় decreasing থাকে, আর front-টাই current window-র max।

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

একটা collections.deque যেটা index রাখে (value নয়)। index রাখলে দুটো সুবিধা: (১) front কখন window থেকে বেরিয়ে গেছে (expired) সেটা index <= i - k দিয়ে ধরা যায়, আর (২) দরকারে nums[index] দিয়ে value পাওয়া যায়। deque লাগে কারণ আমাদের দুই প্রান্তেই O(1) operation চাই — back-এ push/pop (dominated eject) আর front-এ pop (expired)।

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

সাধারণ list-এ সামনের প্রান্ত থেকে pop O(n) (সব element সরাতে হয়); deque দুই প্রান্তেই O(1) দেয়। এখানে দুই ধরনের exit দরকার — back থেকে (নতুন কেউ এসে useless বানালো) আর front থেকে (window পেরিয়ে গেল)। দুটোই O(1) বলে প্রতিটা index জীবনে বড়জোর একবার push আর একবার pop হয় → পুরো কাজ O(n)।

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

প্রথম সরল উপায়¶

সবচেয়ে সরল চিন্তা: প্রতিটা window-র জন্য আলাদা করে তার k-টা element scan করে max বের করি।

উদাহরণ

for start in range(len(nums) - k + 1):
    answer.append(max(nums[start : start + k]))

কোথায় বেশি কাজ হচ্ছে¶

প্রায় n টা window, প্রতিটার জন্য k-টা element আবার scan → O(n*k)। n = 10^5, k = 10^4 হলে এটা প্রায় 10^9 step। একই element বারবার বিভিন্ন window-র scan-এ পড়ে যায় — পুরো অপচয়। আমরা চাই প্রতিটা element-কে বড়জোর একবার push আর একবার pop করে O(n)-তে কাজ সারতে।

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

মূল observation: একটা window-র ভেতরে একটা ছোট element-এর ডান পাশে যদি তার চেয়ে বড় (বা সমান) আর নতুন element থাকে, তবে সেই ছোট element আর কোনোদিন কোনো window-র max হবে না। তাই max খোঁজার জন্য সব element রাখার দরকার নেই — শুধু "এখনো দাবিদার" decreasing chain-টা রাখলেই front-এ উত্তর তৈরি থাকে।

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

array-তে একবার বাঁ-থেকে-ডান হাঁটো, index-এর একটা deque রেখে। নতুন i এলে: (১) deque-র back থেকে যাদের value nums[i]-এর <=, তাদের সবাইকে pop করো (useless); (২) i push করো back-এ; (৩) front-এর index যদি i - k-এর সমান বা ছোট হয় (window পেরিয়ে গেছে), front pop করো; (৪) i >= k - 1 হলে (প্রথম পূর্ণ window তৈরি) nums[front] answer-এ যোগ করো — front-ই max।

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

মোচড়: "প্রতিটা window নতুন করে scan করব" — এভাবে ভেবো না। ভাবো "আমি একটা ছোট দল রাখব, যেখানে শুধু এখনো-জেতার-সম্ভাবনা-আছে এমন রাই থাকবে, শক্তির ক্রমে সাজানো"। নতুন কেউ এলে দুর্বলদের সাথে সাথে ছাঁটো; মেয়াদ ফুরালে সামনের জনকে বিদায়। তখন max খুঁজতে কখনোই scan করতে হয় না — সবসময় front-এ তৈরি।

ছবিতে বোঝা¶

[1, 3, -1, -3, 5, 3, 6, 7], k = 3-এর জন্য deque-তে (index রাখা, তবে নিচে value দেখানো; front বাঁয়ে) কী ঘটে:

উদাহরণ

i  val  deque after step (values)    window           max (front)
0   1   [1]                          —                —
1   3   [3]      (1 ejected: <=3)    —                —
2  -1   [3,-1]                       [1, 3,-1]        3
3  -3   [3,-1,-3]                    [3,-1,-3]        3
4   5   [5]      (front 3 expired; -3,-1 ejected)
                                     [-1,-3, 5]       5
5   3   [5,3]                        [-3, 5, 3]       5
6   6   [6]      (3 and 5 ejected)   [5, 3, 6]        6
7   7   [7]      (6 ejected)         [3, 6, 7]        7

answer: [3, 3, 5, 5, 6, 7]

(একই trace ../patterns.md Pattern 5-এ আছে।)

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

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

i=0 (9): deque খালি, push → [0]। front 0 <= 0-2? না। i >= 1? না।
i=1 (8): nums[0]=9 <= 8? না, push → [0,1]। front 0 <= -1? না। i>=1: answer += nums[0]=9 → [9]
i=2 (7): nums[1]=8 <= 7? না, push → [0,1,2]। front 0 <= 0? হ্যাঁ → popleft → [1,2]। answer += nums[1]=8 → [9,8]
i=3 (6): nums[2]=7 <= 6? না, push → [1,2,3]। front 1 <= 1? হ্যাঁ → popleft → [2,3]। answer += nums[2]=7 → [9,8,7]
return [9, 8, 7]

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

Python¶

Python

from collections import deque

def max_sliding_window(nums, k):
    if not nums or k == 0:
        return []
    dq = deque()                              # index রাখে; value front->back এ কমতে থাকে
    result = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:       # x-এর <= back-রা চিরতরে useless
            dq.pop()
        dq.append(i)                          # x নিজে এখন দাবিদার
        if dq[0] <= i - k:                    # front window থেকে বেরিয়ে গেছে
            dq.popleft()
        if i >= k - 1:                        # প্রথম পূর্ণ window থেকে answer নেওয়া শুরু
            result.append(nums[dq[0]])         # front-টাই current window-র max
    return result

# ---- tests ----
assert max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]
assert max_sliding_window([9, 8, 7, 6], 2) == [9, 8, 7]
assert max_sliding_window([4, 4, 4, 4], 2) == [4, 4, 4]   # সমান value-ও ঠিক
assert max_sliding_window([1, 5, 2], 1) == [1, 5, 2]      # k=1
assert max_sliding_window([1, 3, -1], 3) == [3]           # k=len
assert max_sliding_window([], 3) == []                    # খালি
print("সব test pass!")

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

if not nums or k == 0: return [] — খালি input বা k=0-এ কিছু করার নেই।
dq = deque() — index জমবে, value নয়; index থাকলে expiry আর value দুটোই পাওয়া যায়।
while dq and nums[dq[-1]] <= x: / dq.pop() — নতুন x-এর <= সব back-element চিরতরে useless, পেছন থেকে ফেলে দাও (<= বলে সমান value-ও সরে, তাতে front সবসময় সাম্প্রতিকতমটা থাকে)।
dq.append(i) — x এখন একজন দাবিদার, back-এ যোগ।
if dq[0] <= i - k: dq.popleft() — front-এর index যদি window-র বাঁ সীমার বাইরে পড়ে যায়, সামনের দরজা দিয়ে বিদায়। (প্রতি step-এ বড়জোর একজনই expire করে, তাই if-ই যথেষ্ট, while লাগে না।)
if i >= k - 1: result.append(nums[dq[0]]) — index k-1 থেকে প্রতিটা পূর্ণ window-র জন্য front-এর value-ই max।

Output মিলিয়ে দেখা¶

max_sliding_window([1,3,-1,-3,5,3,6,7], 3) → section 7-এর trace মতো প্রতিটা window-র max [3,3,5,5,6,7]। max_sliding_window([4,4,4,4], 2) → <= comparison-এর কারণে পুরোনো সমান 4-গুলো eject হয়ে front-এ সবসময় সাম্প্রতিকতম 4 থাকে, ফল [4,4,4]। সব assert pass করে শেষে print: সব test pass!।

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

সময়¶

O(n) — প্রতিটা index ঠিক একবার deque-তে push হয় আর বড়জোর একবার pop হয় (back থেকে beaten হয়ে, বা front থেকে expired হয়ে)। মোট deque operation ≤ 2n, যেকোনো step যতগুলো ejection ঘটাক না কেন। Naive O(n*k)-র তুলনায় বিশাল লাভ।

অতিরিক্ত জায়গা¶

O(k) — deque-তে একসাথে বড়জোর k-টা index থাকতে পারে (একটা window-র সমান), কারণ পুরোনোরা expire হয়ে যায়। output list আলাদা করে ধরা হয় না।

যে ভুলগুলো এড়াতে হবে¶

deque-তে value রাখা, index নয় — তখন front কখন expire করল সেটা ধরা যায় না।
< বনাম <= — back eject-এ <= দরকার যাতে সমান value-র পুরোনোটা সরে; < দিলে duplicate জমে front পুরোনো index ধরে রাখতে পারে।
expiry check করতে while ব্যবহার করা ভুল নয়, কিন্তু if-ই যথেষ্ট — প্রতি step-এ বড়জোর একজন front-element expire করে।
i >= k - 1 শর্ত ভুলে গিয়ে অসম্পূর্ণ প্রথম window-গুলোর জন্যও answer যোগ করা।

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

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

ভিত্তি: sliding window basic (../../02-arrays-and-strings/) + queue, একসাথে monotonic deque-তে রূপান্তরিত — ../patterns.md Pattern 5 (chapter-এর required centerpiece)। dominance idea-টা Pattern 4 (monotonic stack)-এর জ্ঞাতি; পার্থক্য শুধু এখানে element front থেকেও (expire হয়ে) বেরোয়।

পরের অনুশীলন¶

Shortest Subarray with Sum at Least K (prefix sum-এর উপর monotonic deque) — https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/ (এই tracker-এর #23)
Constrained Subsequence Sum (deque-optimized DP) — https://leetcode.com/problems/constrained-subsequence-sum/
Sliding Window Median — https://leetcode.com/problems/sliding-window-median/

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

Monotonic deque: "প্রতিটা k-window-র max/min", "শেষ k item-এর best value" দেখলে index-এর একটা decreasing (max-এর জন্য) deque রাখো — নতুন এসে dominated back-দের eject করো, expired front pop করো, front-ই answer। min চাইলে comparison উল্টাও।

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

ভবিষ্যতের আমাকে: deque হলো "কোনোদিন max হতে পারি" দের waiting room, value front→back কমতে থাকে। নতুন এসে নিজের <= দের পেছন থেকে ছাঁটো, push করো, front expired হলে সামনে থেকে ছাঁটো, i >= k-1 থেকে front-কে answer হিসেবে নাও। index রাখো (value নয়), back-এ <=। "max/min of every window" দেখলেই এই pattern — chapter-এর centerpiece, scratch থেকে re-derive করতে পারা চাই।

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