023 — Sliding Window Maximum

Problem link ও উৎস

• Original source: Classic monotonic-deque exercise
• Platform: LeetCode — https://leetcode.com/problems/sliding-window-maximum/
• Topic: array / monotonic deque
• Difficulty: Hard
• Pattern: monotonic deque (descending)
• Basic idea inherited from: sliding window + queue — পূর্ণ walkthrough ../../04-stack-and-queue/patterns.md-তে

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

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

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

উদাহরণ

nums = [1,3,-1,-3,5,3,6,7], k = 3
windows: [1,3,-1]=3, [3,-1,-3]=3, [-1,-3,5]=5,
         [-3,5,3]=5,  [5,3,6]=6,  [3,6,7]=7
ফল: [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,11], k = 2              -> [11]

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

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

ভাবো একসারি লোক উচ্চতা নিয়ে দাঁড়িয়ে, তুমি সামনে থেকে দেখছ। নতুন কেউ পেছনে এসে দাঁড়ালে, তার সামনের যারা তার চেয়ে বেঁটে, তারা আর "সবচেয়ে লম্বা" হওয়ার দৌড়ে নেই — কারণ এই নতুন লম্বা জন যতক্ষণ আছে, ততক্ষণ তাদের ছাপিয়ে যাবে। তাই বেঁটেদের সারি থেকে সরিয়ে দাও। সারির একদম সামনে সবসময় এই মুহূর্তের সবচেয়ে লম্বা জন।

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

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

ভিত sliding window (problem 10) আর queue (FIFO)। সাধারণ window-এ প্রতিবার max খুঁজতে গেলে O(k) লাগে; এখানে চালাকি হলো একটা monotonic deque (দুই দিকে খোলা queue) রাখা, যেখানে শুধু "ভবিষ্যতে কাজে লাগতে পারে এমন candidate"-রা descending order-এ থাকে। queue + sliding window-এর পূর্ণ গল্প ../../04-stack-and-queue/patterns.md-তে — এই problem সেই অধ্যায়ে hand-off করে।

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

লুকানো logic একটা domination নিয়ম: window-এ যদি কোনো নতুন element x আসে আর তার বাঁয়ে এমন কেউ থাকে যে x-এর চেয়ে ছোট-বা-সমান, তবে সেই ছোট জনের আর কোনো ভবিষ্যৎ নেই — যতক্ষণ সে window-এ থাকবে, x-ও থাকবে এবং বড়। তাই তাকে চিরতরে বাদ দেওয়া যায়। ফলে deque সবসময় strictly descending থাকে, আর তার সামনে (front) থাকে চলতি window-এর সর্বোচ্চ।

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

একটা deque (collections.deque), যা element-এর index রাখে (মান নয়, যাতে কে window থেকে বেরিয়ে গেছে তা index দিয়ে বোঝা যায়)। deque-এর index-গুলোর মানগুলো সামনে-থেকে-পেছনে descending। সাথে output list।

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

দুই দিকে কাজ লাগে: পেছনে (back) ছোট candidate বাদ দিতে হয় (নতুন বড় element এলে), আর সামনে (front) থেকে window-ছাড়া পুরোনো index বাদ দিতে হয়। deque দুই প্রান্তেই O(1) push/pop দেয় — তাই দুটো কাজই দ্রুত। index রাখায় "front-এর element কি এখনো window-এ?" তা front <= i-k দিয়ে যাচাই করা যায়।

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

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

প্রথম সরল চিন্তা: প্রতিটা window-অবস্থানের জন্য সেই k-টা element-এর মধ্যে max() আলাদা করে বের করো।

উদাহরণ

res = []
for i in range(n - k + 1):
    res.append(max(nums[i : i + k]))

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

প্রতিটা window-এ আবার k-টা element scan করে max — মোট O(n·k)। k বড় হলে অসহনীয় ধীর, আর প্রতিবার আগের window-এর কাজ ফেলে দিয়ে নতুন করে গোনা হচ্ছে। monotonic deque সেই কাজ পুনর্ব্যবহার করে: প্রতিটা index ঠিক একবার ঢোকে, একবার বের হয় → O(n)।

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

মূল observation: একটা element যদি তার ডানে আসা কোনো element-এর চেয়ে ছোট-বা-সমান হয়, তবে সে আর কখনো window-max হতে পারবে না (ডানের বড়জন তাকে সবসময় ছাপাবে যতক্ষণ দুজনই window-এ)। তাই এমন "ছাপিয়ে যাওয়া" candidate-দের রাখার দরকার নেই — deque-কে descending রাখলে front-ই max।

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

প্রতিটা index i (মান x)-এ:

• পেছন পরিষ্কার: deque-এর শেষের index-গুলোর মান <= x হলে pop (তারা আর দরকারি নয়); তারপর i push।
• সামনে পরিষ্কার: front index যদি window ছেড়ে গেছে (front == i - k), তবে popleft।
• উত্তর: i >= k-1 হলে window পূর্ণ — front-এর মানই (nums[deque[0]]) এই window-এর max, output-এ রাখো।

প্রতিটা index একবার push, একবার pop → মোট O(n)।

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

মোচড়: "প্রতিটা window-এ max আবার খুঁজব" (O(n·k)) ভোলো। ভাবো "একটা candidate-সারি রাখব, যেখান থেকে নিশ্চিত-হেরে-যাওয়া (ছোট) লোকদের ছেঁটে ফেলি; তাহলে সারির সামনেই সবসময় বর্তমান max।" max খোঁজা গায়েব হয়ে একটা O(1) "front দেখা"-তে নেমে আসে।

ছবিতে বোঝা

nums = [1,3,-1,-3,5,3,6,7], k = 3 — deque-এ index (মান descending), front = window max:

উদাহরণ

i=0 v=1 : deque idx[0]                        (মান 1)
i=1 v=3 : 1<=3 পেছন pop; deque idx[1]          (মান 3)
i=2 v=-1: deque idx[1,2] -> window পূর্ণ, max=nums[1]=3
i=3 v=-3: deque idx[1,2,3]; front 1==3-3 বাইরে? না(=0?) -> max=nums[1]=3
i=4 v=5 : -3,-1,3 সব<=5 pop; deque idx[4]; max=nums[4]=5
i=5 v=3 : deque idx[4,5]; max=nums[4]=5
i=6 v=6 : 3,5<=6 pop; deque idx[6]; max=nums[6]=6
i=7 v=7 : 6<=7 pop; deque idx[7]; max=nums[7]=7
ফল: [3,3,5,5,6,7]

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

Input nums = [9, 11], k = 2:

1. i=0 x=9: deque খালি → push 0 → deque=[0]। front 0 == 0-2? না। i >= k-1(0>=1)? না।
2. i=1 x=11: পেছন nums[0]=9 <= 11 → pop; push 1 → deque=[1]। front 1 == 1-2? না। i>=1? হ্যাঁ → res.append(nums[1]=11)।
3. শেষ। ফল: [11]।

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

Python

Python

from collections import deque

def max_sliding_window(nums, k):
    if not nums:
        return []
    dq = deque()                       # index রাখে; মানগুলো descending
    result = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()                   # ছোট candidate চিরতরে বাদ
        dq.append(i)
        if dq[0] == i - k:             # front window ছেড়ে গেছে
            dq.popleft()
        if i >= k - 1:                 # window পূর্ণ -> front = max
            result.append(nums[dq[0]])
    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, 11], 2) == [11]
assert max_sliding_window([1, -1], 1) == [1, -1]   # k = 1
assert max_sliding_window([], 3) == []             # খালি
print("সব test pass!")

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

• if not nums: return [] — খালি input-এ কোনো window নেই।
• dq = deque() — index-এর monotonic (descending-মান) queue।
• while dq and nums[dq[-1]] <= x: dq.pop() — নতুন x-এর চেয়ে ছোট-সমান পেছনের candidate-রা চিরতরে অপ্রয়োজনীয়, বাদ।
• dq.append(i) — নতুন index পেছনে যোগ।
• if dq[0] == i - k: dq.popleft() — front-এর index window-এর বাঁ সীমা পেরিয়ে গেলে সামনে থেকে বাদ।
• if i >= k - 1: result.append(nums[dq[0]]) — প্রথম পূর্ণ window থেকে শুরু করে প্রতিবার front-এর মান (= current max) রাখি।
• return result — প্রতিটা window-এর max-এর list।

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

[1,3,-1,-3,5,3,6,7], k=3 → deque front ধরে রাখে চলতি max; ছোটরা বাদ পড়ে, পুরোনো index window ছাড়লে front থেকে যায় → [3,3,5,5,6,7], assert pass। [9,11], k=2 → [11]; [1,-1], k=1 → প্রতিটা একাই window → [1,-1]; [], k=3 → []। শেষে print: সব test pass!।

JavaScript ও test cases

index-এর monotonic deque (descending মান) — array দিয়ে দুই প্রান্তে push/pop।

JavaScript

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
// max of each k-sized sliding window (monotonic deque of indices)
function maxSlidingWindow(nums, k) {
  if (nums.length === 0) return [];
  const dq = [];                       // index রাখে; মানগুলো descending
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();  // ছোট বাদ
    dq.push(i);
    if (dq[0] === i - k) dq.shift();    // front window ছেড়ে গেছে
    if (i >= k - 1) result.push(nums[dq[0]]);  // window পূর্ণ -> front = max
  }
  return result;
}
// ---- test cases (example + edge) ----
assert(eq(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3), [3, 3, 5, 5, 6, 7]), "classic");
assert(eq(maxSlidingWindow([9, 11], 2), [11]), "two");
assert(eq(maxSlidingWindow([1, -1], 1), [1, -1]), "k=1");        // edge
assert(eq(maxSlidingWindow([], 3), []), "empty");                // edge
console.log("সব JS test pass!");

JS টীকা: deque হিসেবে সাধারণ array — পেছনে push/pop, সামনে shift (front-pop)। অবশ্যই index রাখো, মান নয় — তাহলেই dq[0] === i - k দিয়ে front window ছেড়েছে কিনা বোঝা যায়। array compare-এ JSON.stringify।

TypeScript ও test cases

TypeScript

function maxSlidingWindow(nums: number[], k: number): number[] {
  if (nums.length === 0) return [];
  const dq: number[] = [];                      // indices, values descending
  const result: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
    dq.push(i);
    if (dq[0] === i - k) dq.shift();
    if (i >= k - 1) result.push(nums[dq[0]]);
  }
  return result;
}
function expectArr(actual: number[], exp: number[], msg = ""): void {
  if (JSON.stringify(actual) !== JSON.stringify(exp))
    throw new Error(`FAIL ${msg}: got ${JSON.stringify(actual)}`);
}
expectArr(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3), [3, 3, 5, 5, 6, 7], "classic");
expectArr(maxSlidingWindow([1, -1], 1), [1, -1], "k=1");
expectArr(maxSlidingWindow([], 3), [], "empty");
console.log("সব TS test pass!");

TS টীকা: dq: number[] declare করায় deque-তে শুধু index (number) ঢোকে; nums[dq[...]] access-ও number, তাই domination compare টাইপে নিশ্চিত — মান বনাম index গুলিয়ে ফেলার bug আটকায়।

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

সময়

O(n) — প্রতিটা index ঠিক একবার deque-এ ঢোকে আর বড়জোর একবার বের হয়; তাই সব push/pop মিলিয়ে মোট কাজ linear, k-নিরপেক্ষ।

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

O(k) — deque-এ একসাথে বড়জোর k-টা index থাকে (output আলাদা ধরলে)।

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

• deque-এ মান রাখা, index নয় — তখন front window ছেড়েছে কিনা (== i-k) বোঝা যায় না।
• পেছনে pop-এ < ব্যবহার করে সমান মান রেখে দেওয়া — কাজ করে, কিন্তু <= রাখলে duplicate কম, পরিষ্কার; তবে সমান হলে দুটোই রাখলেও উত্তর ঠিক, শুধু front-pop সাবধানে।
• i >= k-1 শর্ত ভুলে শুরুর অসম্পূর্ণ window-গুলোতেও output দেওয়া।
• front-pop শর্ত dq[0] < i-k+1-এর বদলে ভুল সীমা দেওয়া — window range [i-k+1 .. i], তাই dq[0] == i-k মানে ঠিক বাঁ-সীমার এক ঘর বাইরে।

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

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

ভিত্তি: sliding window (Longest Unique Substring #10)-এর "প্রতিটা index একবার ঢোকে-বেরোয়" + queue-এর FIFO/দুই-প্রান্ত operation। পূর্ণ deque-গল্প ../../04-stack-and-queue/patterns.md-তে; chapter-এর ../patterns.md-এর "Pattern 2 — Sliding Window"-এর এটাই hard শিখর, যা stack/queue অধ্যায়ে hand-off করে।

পরের অনুশীলন

• Sliding Window Minimum (একই deque, ascending) — দেখো ../../04-stack-and-queue/patterns.md
• Shortest Subarray with Sum at Least K (deque + prefix sum) — https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/
• Jump Game VI (deque দিয়ে DP optimize) — https://leetcode.com/problems/jump-game-vi/

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

Monotonic deque: "প্রতিটা window/range-এর max বা min দ্রুত চাই" দেখলে একটা monotonic deque রাখো — নতুন element এলে পেছন থেকে দুর্বল candidate ছাঁটো, সামনে থেকে মেয়াদোত্তীর্ণ index ফেলো; front-ই উত্তর — O(n), k-নিরপেক্ষ।

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

ভবিষ্যতের আমাকে: "window max = index-এর descending deque; নতুন বড় এলে পেছনের ছোটদের pop, window ছাড়লে front popleft, front = max।" "প্রতিটা sliding window-এর max/min" দেখলেই monotonic deque মনে করবে — O(n), আর এখান থেকেই stack/queue অধ্যায় শুরু।

কোথায় কাজে লাগে

• Streaming max/min: চলমান window-তে real-time সর্বোচ্চ/সর্বনিম্ন (rolling extremum) O(1)-এ ধরে রাখা।
• Stock/metrics: সাম্প্রতিক k সময়ের সর্বোচ্চ দাম/লোড দ্রুত track করা।
• Anomaly detection: rolling window-এ peak detect করে threshold-ভঙ্গ চিহ্নিত।
• Networking: সাম্প্রতিক k packet-এ সর্বোচ্চ latency/throughput monitor।
• Audio/DSP: moving-window peak normalization।
• DP optimization: monotonic deque দিয়ে sliding-window DP (যেমন Jump Game VI) দ্রুত করা।

মূল pattern: monotonic deque রাখো — নতুন বড় এলে পেছনের দুর্বল candidate ছাঁটো, মেয়াদোত্তীর্ণ index সামনে থেকে ফেলো, front-ই উত্তর — O(n), k-নিরপেক্ষ।

---

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