Sliding Window Maximum

42
0

Problem Statement

An integer array nums and a positive integer k are given. A window containing exactly k consecutive elements starts at the left end of the array and moves right by one position at a time.

Return an array containing the maximum value from every valid window, in left-to-right window order.

Example 1

Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
Explanation: The consecutive windows are [1, 3, -1], [3, -1, -3], [-1, -3, 5], [-3, 5, 3], [5, 3, 6], and [3, 6, 7]. The corresponding maximum values are 3, 3, 5, 5, 6, and 7.

Example 2

Input: nums = [4], k = 1
Output: [4]
Explanation: The only window contains the single value 4, so the window maximum equals 4.

Brute Force Approach

Each window contains exactly k elements, and its answer is the largest value among them. The simplest method is to consider every window separately and scan all its elements to find the maximum.

This approach is easy to understand and works well as a basic solution. However, nearby windows contain many common elements, so the same comparisons are repeated multiple times.

Algorithm

  • Create an empty answer array to store the maximum value of every valid window.

  • Traverse each possible starting index from 0 to n - k, because these positions form all windows of size k.

  • Set windowMaximum to the first value of the current window, providing an initial maximum.

  • Scan the remaining elements from start + 1 to start + k - 1.

  • Update windowMaximum whenever a larger value is found, so it always stores the maximum of the current window.

  • Add windowMaximum to the answer array after checking all k elements.

  • Return the completed answer array after processing every window.

Dry Run

Sliding Window Maximum Brute Force

Sliding Window Maximum Brute Force

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds each window maximum by direct scanning.
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
vector<int> answer;
// Examine every valid window from left to right.
for (int start = 0; start <= n - k; start++) {
int windowMaximum = nums[start];
// Compare all remaining values in the window.
for (int index = start + 1; index < start + k; index++) {
// A larger value becomes the current maximum.
if (nums[index] > windowMaximum) {
windowMaximum = nums[index];
}
}
// Save the maximum for the current window.
answer.push_back(windowMaximum);
}
return answer;
}
};
// Driver code
int main() {
vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
Solution obj;
vector<int> answer = obj.maxSlidingWindow(nums, k);
for (int value : answer) {
cout << value << " ";
}
cout << endl;
return 0;
}

Note: Brute force may fail for large arrays. Repeated window scans create quadratic work when k grows with n, so an online judge may report Time Limit Exceeded.

Complexity Analysis

Time Complexity: O(N × k), up to N values are inspected for each of the N - k + 1 windows.

Space Complexity: O(N - k + 1), the returned answer stores one maximum per valid window, while auxiliary working space is O(1).

Better Approach

The brute-force method repeatedly scans all k elements of every window. A max-heap avoids this repeated scan by keeping the largest inserted value at the top. Each value is stored with its index so its window validity can also be checked.

Some expired values may remain inside the heap, but they do not matter unless they reach the top. Before recording an answer, remove every expired top entry. After this cleanup, the heap top gives the maximum value of the current window.

Algorithm

  • Create an empty max-heap to store value-index pairs and an empty answer array for window maximums.

  • Traverse the array from left to right, so each new value can enter the current window.

  • Insert the current value with its index into the heap, because the index is needed to detect expired entries.

  • Calculate the current window start as index - k + 1.

  • Remove heap-top entries while their index is smaller than the window start, because such values no longer belong to the current window.

  • Do not collect an answer before index reaches k - 1, because a complete window of size k has not formed yet.

  • Add the heap-top value to the answer array for every complete window, because it is the largest valid value currently stored.

  • Return the completed answer array after processing all elements.

Dry Run

Sliding Window Max Better

Sliding Window Max Better

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds each window maximum with a max-heap.
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
vector<int> answer;
priority_queue<pair<int, int>> candidates;
// Add each value and clean expired heap leaders.
for (int index = 0; index < n; index++) {
candidates.push({nums[index], index});
int windowStart = index - k + 1;
// Remove leaders outside the current window.
while (!candidates.empty() &&
candidates.top().second < windowStart) {
candidates.pop();
}
// A complete window has a valid heap leader.
if (index >= k - 1) {
answer.push_back(candidates.top().first);
}
}
return answer;
}
};
// Driver code
int main() {
vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
Solution obj;
vector<int> answer = obj.maxSlidingWindow(nums, k);
for (int value : answer) {
cout << value << " ";
}
cout << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N × log N), every value enters the heap once and every removed value costs at most logarithmic time in a heap containing up to N lazily retained entries.

Space Complexity: O(N), lazy removal can leave expired entries below the heap top, and the returned answer also contains N - k + 1 values.

Optimal Approach

The heap keeps many candidates without using the known left-to-right expiry order. A deque can keep only useful indices. Values decrease from the front to the back, so the front always represents the largest value in the current window.

An incoming value removes every smaller or equal value from the back. Every removed value is both older and no larger, so no future window can prefer the removed value. Expired indices leave from the front, giving constant-time access to each window maximum.

Algorithm

  • Initialize an empty deque of indices and an empty answer array to store maximum values for complete windows.

  • Traverse every array index from left to right, treating the current index as the incoming end of the active window.

  • Remove the front index when the stored index is at most index - k, because the corresponding value has moved outside the current window.

  • Remove indices from the deque back while corresponding values are smaller than or equal to the incoming value, because such values cannot become future window maximums.

  • Push the incoming index at the deque back, maintaining values in decreasing order from front to back.

  • Append the value at the deque-front index after index reaches k - 1, because the front always stores the maximum value of the complete window.

  • Return the completed answer array after processing every array index once.

Dry Run

Sliding Window Max Optimal

Sliding Window Max Optimal

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds each window maximum with a monotonic deque.
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
vector<int> answer;
deque<int> candidates;
// Maintain useful indices for every window end.
for (int index = 0; index < n; index++) {
// Remove the index after the matching value expires.
if (!candidates.empty() && candidates.front() <= index - k) {
candidates.pop_front();
}
// Remove values dominated by the incoming value.
while (!candidates.empty() &&
nums[candidates.back()] <= nums[index]) {
candidates.pop_back();
}
candidates.push_back(index);
// A complete window takes the front value.
if (index >= k - 1) {
answer.push_back(nums[candidates.front()]);
}
}
return answer;
}
};
// Driver code
int main() {
vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
Solution obj;
vector<int> answer = obj.maxSlidingWindow(nums, k);
for (int value : answer) {
cout << value << " ";
}
cout << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), every index enters the deque once and leaves from either end at most once.

Space Complexity: O(k + N - k + 1), the deque stores at most k indices and the returned answer stores one value per valid window; auxiliary working space is O(k).

Interview follow-up Questions

Indices allow the algorithm to check whether an element has moved outside the current window. They also distinguish equal values appearing at different positions, which values alone cannot do.

StackTCS NQT

Read Similar Blogs

Comments0