Python – Sliding Window Maximum (Monotonic Queue Trick) 🚀 #PythonDSA #SlidingWindow

🧠 Problem Given an array nums and a window size k, find the maximum element in every window of size k. Example: nums = [1,3,-1,-3,5,3,6,7] k = 3 Output: [3,3,5,5,6,7] ❌ Brute Force For every window: Take max of k elements Time complexity: O(n * k) ✅ Optimal Approach – Monotonic Queue (Deque) Key idea: Maintain a deque in decreasing order So: Front always = maximum element Remove smaller elements from back 🧠 Why This Works Each element enters and leaves deque only once Ensures O(n) complexity 🔥 Core Logic Remove elements outside window Remove smaller elements (not useful) Add current element Front = maximum 🧪 Example Walkthrough nums = [1,3,-1,-3,5] k = 3 Window evolution: [1,3,-1] → 3 [3,-1,-3] → 3 [-1,-3,5] → 5 ⏱️ Complexity Approach Time Space Brute O(nk) O(1) Deque O(n) O(k) 🧠 Concepts Used ✔ Sliding Window ✔ Monotonic Queue ✔ Deque (Double-ended queue) ✔ Greedy optimization ✔ Two pointers 🎯 Interview Importance This pattern is used in: Sliding window problems Stock problems Range queries Real-time analytics Maximum/minimum tracking 🎤 Interview Questions & Answers Q1. Why use deque instead of heap? Deque gives O(n), heap gives O(n log k) Q2. Why remove smaller elements? They will never be maximum in future windows Q3. Why store indices instead of values? To track window boundaries Q4. What is monotonic queue? A queue that maintains sorted order (increasing/decreasing) Q5. Can we solve using heap? Yes, but slower and less optimal 🧰 Real-World Applications Real-time stock analysis Signal processing CPU load monitoring Streaming data systems Sliding analytics Codes: # 🔄 Brute Force (O(n * k)) def max_sliding_window_naive(nums, k): result = [] for i in range(len(nums) - k + 1): result.append(max(nums[i:i+k])) return result # ⚡ Optimal: Monotonic Deque (O(n)) from collections import deque def max_sliding_window(nums, k): deq = deque() # stores indices result = [] for i in r