023 — Sliding Window Maximum

Source

• 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-তে

1. Problem in simple words

একটা 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]

2. Which basic idea does this inherit from?

ভিত 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 করে।

3. What is the hidden math or logic?

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

4. Which data structure is needed?

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

5. Why this data structure fits

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

6. Real-life analogy

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

7. Visual explanation

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]

8. Example input and 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   -> []

9. Brute force thinking

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

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

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

প্রতিটা 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)।

13. Thinking tweak

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

14. Step-by-step dry run

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]।

15. Python solution

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!")

16. Line-by-line code explanation

• 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।

17. Output walkthrough

[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!।

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

• 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 মানে ঠিক বাঁ-সীমার এক ঘর বাইরে।

21. Which basic problem this inherits from

ভিত্তি: 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 করে।

22. Similar harder problems

• 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/

23. Pattern learned

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

24. Final summary

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

25. JavaScript solution (with test cases)

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

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।

26. TypeScript solution (with test cases)

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 আটকায়।

27. কোথায় কাজে লাগে (real-world use)

• 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।