1. Problem Statement

The Sliding Window Maximum problem asks us to find the maximum element in every contiguous subarray (window) of a fixed size k within a given array nums.

As the window slides from the extreme left of the array to the extreme right by one position at a time, you can only see k numbers in the window. Your goal is to return an array containing the maximum value of each window state.

Key constraints to consider:

• You are given an array of integers nums.
• You are given an integer k representing the window size.
• 1≤k≤nums.length.

2. Examples

Example 1

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

Example 2

Input: nums = [1, -1], k = 1 Output: [1, -1] Explanation: When window size is 1, the maximum of each window is simply the element itself.

3. Brute Force Approach

Intuition

The most straightforward way is to simulate the sliding window exactly as described. For every possible starting position of the window, we iterate through the k elements currently in that window and find the maximum.

Data Structures Used

• std::vector<int> to store the result.

Algorithm

1. Create a result array.
2. Loop i from 0 to n - k (the starting index of each window).
3. Initialize a variable max_val to the smallest possible integer.
4. Loop j from i to i + k - 1 (the elements inside the current window).
5. Update max_val = max(max_val, nums[j]).
6. Append max_val to result.
7. Return result.

Step-by-step Dry Run

Input: nums = [1, 3, -1], k = 2

• i = 0: Window is nums[0..1] -> [1, 3]. Inner loop finds max is 3. Result: [3].
• i = 1: Window is nums[1..2] -> [3, -1]. Inner loop finds max is 3. Result: [3, 3].

C++ Implementation

#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

class SolutionBrute {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> result;
        
        // Loop through each possible window starting index
        for (int i = 0; i <= n - k; i++) {
            int max_val = INT_MIN; // Initialize max value for this window
            
            // Traverse the current window of size k
            for (int j = i; j < i + k; j++) {
                // Update max_val with the largest element in the window
                max_val = max(max_val, nums[j]);
            }
            
            // Store the maximum of this window in the result
            result.push_back(max_val);
        }
        
        // Return the list of maximums for each window
        return result;
    }
};

Optimal Approach

The standard O(N) sliding window maximum utilizes a Monotonic Decreasing Deque.

Core Intuition

Imagine a line of people sorted by height. If a taller person joins the line, anyone shorter than them who is ahead of them in the line becomes useless because they can never be the tallest in the group (the new taller person will outlast them as the window moves). We can maintain a queue where elements are strictly decreasing.

Why Double Ended Queue (Deque) is used

We need to remove elements from the back (when a larger element arrives, rendering smaller ones useless) and from the front (when the maximum element slides out of the window boundary). A std::deque supports O(1) insertions and deletions at both ends.

Why we store Indices instead of Values

Storing indices allows us to easily check if the element at the front of the deque has fallen out of the current window (index <= i - k). We can always get the value using nums[index].

Explain every data structure before coding

• std::deque<int> dq: Stores indices of array elements. The elements corresponding to these indices are kept in strictly decreasing order.
• std::vector<int> result: Stores the maximum values for each window.

6. Algorithm

1. Initialize deque<int> dq and vector<int> result.
2. Iterate i through the array from 0 to N-1.
3. Remove Out-of-Bounds: Check if the index at the front of the deque is ≤i−k. If so, dq.pop_front() because it is no longer in the window.
4. Maintain Monotonic Property: While the deque is not empty AND the current element nums[i] is ≥ the element at the back of the deque nums[dq.back()], dq.pop_back(). (Smaller elements are useless now).
5. Add Current: Push the current index i to the back of the deque.
6. Record Result: If the window has hit size k (which happens when i >= k - 1), push nums[dq.front()] to the result array.

7. Complete C++ Code

#include <vector>
#include <deque>

using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        deque<int> dq; // Stores indices of elements, not the actual values
        
        for (int i = 0; i < nums.size(); i++) {
            // 1. Remove the index at the front if it's outside the current window
            if (!dq.empty() && dq.front() == i - k) {
                dq.pop_front();
            }
            
            // 2. Remove indices from the back while their values are <= current element
            // Because the current element is larger and will last longer in the window
            while (!dq.empty() && nums[dq.back()] <= nums[i]) {
                dq.pop_back();
            }
            
            // 3. Add the current element's index to the deque
            dq.push_back(i);
            
            // 4. Once we have processed at least k elements,
            // the front of the deque holds the index of the maximum element for this window
            if (i >= k - 1) {
                result.push_back(nums[dq.front()]);
            }
        }
        
        return result;
    }
};

8. Dry Run

Take the following example: nums = [1, 3, -1, -3, 5, 3], capacity (k) = 3

Final Result: [3, 3, 5, 5]

9. Complexity Analysis

Why it is $O(N)$ Time:

You might see a while loop inside a for loop and think $O(N^2)$. However, look closer at the deque operations. Every index is pushed into the deque exactly once, and popped from the deque at most once. Therefore, the while loop runs at most $N$ times across the entire execution of the program. Amortized, it is $O(1)$ per element, making the total time $O(N)$.

Why it is $O(K)$ Space:

The deque stores indices. Because we constantly pop elements that are out of bounds or strictly smaller, the deque will contain at most $K$ elements at any given time (this worst case happens when the array is strictly decreasing).

10. Visualization

Let's visualize the deque maintaining the monotonic property for window: [3, -1, 5] with $k=3$.

11. Interview Tips

• Common mistakes: Pushing values to the deque instead of indices. If you push values, you have no efficient way to know if an element has fallen out of the left side of your window.
• Edge cases: $K=1$. The algorithm handles it smoothly, but some candidates try to write separate logic for it. Trust the deque logic.
• Why Heap is sub-optimal: A heap takes $O(\log N)$ to process elements and doesn't easily allow removing arbitrary elements when they leave the window unless doing "lazy deletion" which balloons the space to $O(N)$.
• "Useless Elements" Concept: When explaining to an interviewer, heavily emphasize the phrase: "If a new element is larger than previous ones in the window, those previous ones can never be the maximum again. They are useless." This proves you understand the monotonic logic.

video link:

code link:

https://leetcode.com/problems/sliding-window-maximum/description/