Author at SyntaxFlow
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:
nums.k representing the window size.Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 Output: [3, 3, 5, 5, 6, 7]
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.
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.
std::vector<int> to store the result.result array.i from 0 to n - k (the starting index of each window).max_val to the smallest possible integer.j from i to i + k - 1 (the elements inside the current window).max_val = max(max_val, nums[j]).max_val to result.result.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].#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;
}
};
The standard O(N) sliding window maximum utilizes a Monotonic Decreasing Deque.
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.
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.
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].
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.deque<int> dq and vector<int> result.i through the array from 0 to N-1.dq.pop_front() because it is no longer in the window.nums[i] is ≥ the element at the back of the deque nums[dq.back()], dq.pop_back(). (Smaller elements are useless now).i to the back of the deque.k (which happens when i >= k - 1), push nums[dq.front()] to the result array.#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;
}
};
Take the following example: nums = [1, 3, -1, -3, 5, 3], capacity (k) = 3
Final Result: [3, 3, 5, 5]
Why it is Time:
You might see a while loop inside a for loop and think . 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 times across the entire execution of the program. Amortized, it is per element, making the total time .
Why it is Space:
The deque stores indices. Because we constantly pop elements that are out of bounds or strictly smaller, the deque will contain at most elements at any given time (this worst case happens when the array is strictly decreasing).
Let's visualize the deque maintaining the monotonic property for window: [3, -1, 5] with .
video link:
reference video
code link:
https://leetcode.com/problems/sliding-window-maximum/description/