LeetCode Solution 239 - Sliding Window Maximum

Problem Statement

You are given an array nums and an integer k. You need to find the maximum value in every contiguous subarray of size k.

Example:

Input:

nums = [1,3,-1,-3,5,3,6,7], k = 3

Output:

[3,3,5,5,6,7]

Explanation:

Sliding windows and their max values:

[1, 3, -1] → 3
[3, -1, -3] → 3
[-1, -3, 5] → 5
[-3, 5, 3] → 5
[5, 3, 6] → 6
[3, 6, 7] → 7

---

Optimal Approach: Deque (Monotonic Queue)

Why Deque?

• Maintains elements in decreasing order.
• Ensures O(1) access to the maximum.
• Efficient sliding window updates.

Algorithm:

1. Use a deque to store indices of useful elements.
2. Remove elements that fall out of the window.
3. Maintain elements in decreasing order.
4. The front of the deque always holds the max element.

---

C++ Code Implementation

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> result;
        
        for (int i = 0; i < nums.size(); i++) {
            if (!dq.empty() && dq.front() == i - k) {
                dq.pop_front();
            }
            
            while (!dq.empty() && nums[dq.back()] < nums[i]) {
                dq.pop_back();
            }
            
            dq.push_back(i);
            if (i >= k - 1) {
                result.push_back(nums[dq.front()]);
            }
        }
        return result;
    }
};

---

Step-by-Step Explanation

1. Maintain Deque: Store indices in decreasing order.
2. Remove Outdated Elements: If an element is out of the window, remove it.
3. Ensure Order: Maintain the deque in decreasing order.
4. Add Max to Result: Store the max from the front of the deque.

---

Dry Run

Input:

nums = [1,3,-1,-3,5,3,6,7], k = 3

Execution:

Step	Window	Deque (Indices)	Max
1	[1,3,-1]	[1,2]	3
2	[3,-1,-3]	[1,2,3]	3
3	[-1,-3,5]	[4]	5
4	[-3,5,3]	[4,5]	5
5	[5,3,6]	[6]	6
6	[3,6,7]	[7]	7

---

Alternative Approaches

Approach	Time Complexity	Space Complexity	Reason for Rejection
Brute Force	O(N*K)	O(1)	Too slow for large inputs
Priority Queue (Max Heap)	O(N log K)	O(K)	Heap operations add overhead
Deque (Monotonic)	O(N)	O(K)	Best balance

---

Complexity Analysis

• Time Complexity: O(N), each element is pushed/popped once.
• Space Complexity: O(K), for storing indices in deque.

---

Conclusion

• Best Approach: Deque (Monotonic Queue) ensures optimal performance.
• Further Practice:
  • Sliding Window Median
  • Maximum of Minimum for Every Window

This solution efficiently finds the maximum in every sliding window using Deque (Monotonic Queue), making it optimal for large inputs.