Sliding Window Maximum solution and explanation
9 more videos on this problem
Sliding Window Maximum - Monotonic Queue - Leetcode 239NeetCode · 15:46 · 417K views
Sliding Window Maximum | Leetcodetake U forward · 20:16 · 296K views
Sliding Window Maximum | Leetcode #239Techdose · 25:38 · 60K views
Sliding Window Maximum | Monotonic Deque | INTUITIVE | GOOGLE | Leetcode-239 | Dry RuncodestorywithMIK · 31:54 · 46K views
Sliding Window Maximum - Leetcode 239 | Monotonic Deque O(N) | Java & PythonCode With K5KC · 7:46 · 13K views
LeetCode 239: Sliding Window MaximumEngineering Digest · 16:39 · 10K views
Sliding Window Maximum (LeetCode 239) — 48 Companies Ask This! Step-by-Step Deque ApproachNikhil Lohia · 21:22 · 7K views
Sliding Window Maximum | LeetCode 239 (Hard)Destination FAANG · 19:48 · 7K views
Sliding Window Maximum - Leetcode 239 - PythonTechError · 9:19 · 3K views
𝗦𝗹𝗶𝗱𝗶𝗻𝗴 𝗪𝗶𝗻𝗱𝗼𝘄 𝗠𝗮𝘅𝗶𝗺𝘂𝗺 (𝗣𝗮𝗿𝘁 𝟭) | 𝗢(𝗻) 𝗦𝗼𝗹𝘂𝘁𝗶𝗼𝗻 | 𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟮𝟯𝟵 | 𝗣𝗵𝗮𝗻𝗶 𝗧𝗵𝗮𝘁𝗶𝗰𝗵𝗮𝗿𝗹𝗮Phani Thaticharla · 8:30 · 3K views
The problem
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
Example 2:
Input: nums = [1], k = 1 Output: [1]
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
Approach overview
Problem Overview: You are given an array nums and a window size k. As the window slides from left to right, return the maximum element in each window of size k. The challenge is avoiding repeated work when the window shifts by one position.
Approach 1: Brute Force (Time: O(nk), Space: O(1))
The straightforward method evaluates every window independently. Iterate through the array and for each starting index i, scan the next k elements to compute the maximum. This uses simple iteration over the array and does not require extra data structures. While easy to implement and good for understanding the problem mechanics, it repeats comparisons for overlapping windows. With large inputs or large k, the repeated scanning causes the runtime to grow to O(nk), which fails typical interview constraints.
Approach 2: Optimized Deque Method (Time: O(n), Space: O(k))
The optimal solution maintains a decreasing monotonic queue using a deque. Store indices of elements, not the values themselves. While iterating through the array, remove indices from the front if they fall outside the current window. Then remove indices from the back while their corresponding values are smaller than the current element. This guarantees the deque stays in decreasing order of values. The front of the deque always holds the index of the current window's maximum. Each element is inserted and removed at most once, producing O(n) time complexity with O(k) space.
This method is a classic use of a sliding window combined with a queue-like structure. The key insight is maintaining candidates for the maximum while discarding elements that can never become maximums in future windows.
Recommended for interviews: Interviewers expect the monotonic deque solution. The brute force approach demonstrates baseline reasoning, but the optimized method shows mastery of sliding window patterns and amortized analysis. Being able to explain why each index enters and leaves the deque only once is the signal that you understand the optimization.
Approach 1: Approach 1: Brute Force
This approach involves checking each possible window (of length k) one by one and calculating the maximum for each window. This method is straightforward but inefficient for large arrays as it runs in O(n*k) time complexity.
def maxSlidingWindow(nums, k):
result = []
for i in range(len(nums) - k + 1):
result.append(max(nums[i:i+k]))
return result
# Example usage:
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(maxSlidingWindow(nums, k))import java.util.ArrayList;
import java.util.List;
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i <= nums.length - k; i++) {
int max = Integer.MIN_VALUE;
for (int j = i; j < i + k; j++) {
max = Math.max(max, nums[j]);
}
list.add(max);
}
return list.stream().mapToInt(i -> i).toArray();
}
public static void main(String[] args) {
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
Solution solution = new Solution();
int[] result = solution.maxSlidingWindow(nums, k);
for (int num : result) {
System.out.print(num + " ");
}
}
}#include <vector>
#include <climits>
#include <iostream>
using namespace std;
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
for (int i = 0; i <= nums.size() - k; ++i) {
int max_val = INT_MIN;
for (int j = i; j < i + k; ++j) {
max_val = max(max_val, nums[j]);
}
result.push_back(max_val);
}
return result;
}
int main() {
vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
vector<int> result = maxSlidingWindow(nums, k);
for (int num : result) {
cout << num << " ";
}
return 0;
}function maxSlidingWindow(nums, k) {
const result = [];
for (let i = 0; i <= nums.length - k; i++) {
let max = -Infinity;
for (let j = i; j < i + k; j++) {
max = Math.max(max, nums[j]);
}
result.push(max);
}
return result;
}
// Example usage:
const nums = [1, 3, -1, -3, 5, 3, 6, 7];
const k = 3;
console.log(maxSlidingWindow(nums, k));#include <stdio.h>
#include <limits.h>
void maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize, int* result) {
*returnSize = numsSize - k + 1;
for (int i = 0; i <= numsSize - k; ++i) {
int max = INT_MIN;
for (int j = i; j < i + k; ++j) {
if (nums[j] > max) {
max = nums[j];
}
}
result[i] = max;
}
}
int main() {
int nums[] = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
int returnSize;
int result[6];
maxSlidingWindow(nums, 8, k, &returnSize, result);
for (int i = 0; i < returnSize; ++i) {
printf("%d ", result[i]);
}
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] MaxSlidingWindow(int[] nums, int k) {
List<int> result = new List<int>();
for (int i = 0; i <= nums.Length - k; i++) {
int max = Int32.MinValue;
for (int j = i; j < i + k; j++) {
max = Math.Max(max, nums[j]);
}
result.Add(max);
}
return result.ToArray();
}
public static void Main(string[] args) {
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
Solution s = new Solution();
int[] result = s.MaxSlidingWindow(nums, k);
Console.WriteLine(string.Join(" ", result));
}
}In the Python solution, we use a list comprehension to evaluate each window, compute the maximum, and append to the result list, making use of the built-in max function.
Time complexity: O(n*k)
Space complexity: O(n-k+1)
Approach 2: Approach 2: Optimized Deque Method
Use a deque (double-ended queue) to store indices of array elements, which helps in maintaining the maximum for the sliding window in an efficient manner. As the window slides, the method checks and rearranges the deque so that the front always contains the index of the maximum element.
from collections import deque
def maxSlidingWindow(nums, k):
deq = deque()
result = []
for i in range(len(nums)):
if deq and deq[0] < i - k + 1:
deq.popleft()
while deq and nums[deq[-1]] < nums[i]:
deq.pop()
deq.append(i)
if i >= k - 1:
result.append(nums[deq[0]])
return result
# Example usage:
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(maxSlidingWindow(nums, k))import java.util.ArrayDeque;
import java.util.Deque;
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deq = new ArrayDeque<>();
int[] result = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
while (!deq.isEmpty() && deq.peek() < i - k + 1) {
deq.poll();
}
while (!deq.isEmpty() && nums[deq.peekLast()] < nums[i]) {
deq.pollLast();
}
deq.offer(i);
if (i >= k - 1) {
result[i - k + 1] = nums[deq.peek()];
}
}
return result;
}
public static void main(String[] args) {
Solution s = new Solution();
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
int[] result = s.maxSlidingWindow(nums, k);
for (int num : result) {
System.out.print(num + " ");
}
}
}#include <deque>
#include <vector>
#include <iostream>
using namespace std;
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> deq;
vector<int> result;
for (int i = 0; i < nums.size(); ++i) {
if (!deq.empty() && deq.front() == i - k) deq.pop_front();
while (!deq.empty() && nums[deq.back()] < nums[i]) deq.pop_back();
deq.push_back(i);
if (i >= k - 1) result.push_back(nums[deq.front()]);
}
return result;
}
int main() {
vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
vector<int> result = maxSlidingWindow(nums, k);
for (int num : result) {
cout << num << " ";
}
return 0;
}function maxSlidingWindow(nums, k) {
const result = [];
const deq = [];
for (let i = 0; i < nums.length; i++) {
if (deq.length && deq[0] < i - k + 1) deq.shift();
while (deq.length && nums[deq[deq.length - 1]] < nums[i]) deq.pop();
deq.push(i);
if (i >= k - 1) result.push(nums[deq[0]]);
}
return result;
}
// Example usage:
const nums = [1, 3, -1, -3, 5, 3, 6, 7];
const k = 3;
console.log(maxSlidingWindow(nums, k));#include <stdio.h>
#include <stdlib.h>
// Structure of deque
struct Deque {
int* array;
int size, front, rear;
};
struct Deque* createDeque(int size) {
struct Deque* deque = (struct Deque*)malloc(sizeof(struct Deque));
deque->size = size;
deque->front = deque->rear = -1;
deque->array = (int*)malloc(deque->size * sizeof(int));
return deque;
}
int isEmpty(struct Deque* deque) {
return deque->front == -1;
}
int isFull(struct Deque* deque) {
return (deque->rear + 1) % deque->size == deque->front;
}
void insertRear(struct Deque* deque, int element) {
if (isFull(deque)) return;
if (isEmpty(deque)) deque->front = 0;
deque->rear = (deque->rear + 1) % deque->size;
deque->array[deque->rear] = element;
}
void deleteFront(struct Deque* deque) {
if (isEmpty(deque)) return;
if (deque->front == deque->rear) {
deque->front = deque->rear = -1;
} else {
deque->front = (deque->front + 1) % deque->size;
}
}
int getFront(struct Deque* deque) {
if (isEmpty(deque)) return -1;
return deque->array[deque->front];
}
int maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize, int* result) {
*returnSize = numsSize - k + 1;
struct Deque* deque = createDeque(numsSize);
int i;
for (i = 0; i < k; ++i) {
while (!isEmpty(deque) && nums[i] >= nums[getFront(deque)]) {
deleteFront(deque);
}
insertRear(deque, i);
}
for (; i < numsSize; ++i) {
result[i - k] = nums[getFront(deque)];
while (!isEmpty(deque) && getFront(deque) <= i - k) {
deleteFront(deque);
}
while (!isEmpty(deque) && nums[i] >= nums[getFront(deque)]) {
deleteFront(deque);
}
insertRear(deque, i);
}
result[i - k] = nums[getFront(deque)];
free(deque->array);
free(deque);
return 0;
}
int main() {
int nums[] = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
int returnSize;
int result[6];
maxSlidingWindow(nums, 8, k, &returnSize, result);
for (int i = 0; i < returnSize; ++i) {
printf("%d ", result[i]);
}
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] MaxSlidingWindow(int[] nums, int k) {
LinkedList<int> deq = new LinkedList<int>();
List<int> result = new List<int>();
for (int i = 0; i < nums.Length; i++) {
if (deq.Count > 0 && deq.First.Value <= i - k) {
deq.RemoveFirst();
}
while (deq.Count > 0 && nums[deq.Last.Value] < nums[i]) {
deq.RemoveLast();
}
deq.AddLast(i);
if (i >= k - 1) {
result.Add(nums[deq.First.Value]);
}
}
return result.ToArray();
}
public static void Main(string[] args) {
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
Solution s = new Solution();
int[] result = s.MaxSlidingWindow(nums, k);
Console.WriteLine(string.Join(" ", result));
}
}The Python solution uses collections.deque to efficiently maintain indices of elements. The deque is manipulated to ensure operations for determining the maximum and maintaining validity happen in constant time.
Time complexity: O(n)
Space complexity: O(k)
Approach 3: Priority Queue (Max-Heap)
We can use a priority queue (max-heap) to maintain the maximum value in the sliding window.
First, add the first k-1 elements to the priority queue. Then, starting from the k-th element, add the new element to the priority queue and check if the top element of the heap is out of the window. If it is, remove the top element. Then, add the top element of the heap to the result array.
The time complexity is O(n times log k), and the space complexity is O(k). Here, n is the length of the array.
func maxSlidingWindow(nums []int, k int) (ans []int) {
q := hp{}
for i, v := range nums[:k-1] {
heap.Push(&q, pair{v, i})
}
for i := k - 1; i < len(nums); i++ {
heap.Push(&q, pair{nums[i], i})
for q[0].i <= i-k {
heap.Pop(&q)
}
ans = append(ans, q[0].v)
}
return
}
type pair struct{ v, i int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool {
a, b := h[i], h[j]
return a.v > b.v || (a.v == b.v && i < j)
}
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }Approach 4: Monotonic Queue
To find the maximum value in a sliding window, a common method is to use a monotonic queue.
We can maintain a queue q that is monotonically decreasing from the front to the back, storing the indices of the elements. As we traverse the array nums, for the current element nums[i], we first check if the front element of the queue is out of the window. If it is, we remove the front element. Then, we compare the current element nums[i] with the elements at the back of the queue. If the elements at the back are less than or equal to the current element, we remove them until the element at the back is greater than the current element or the queue is empty. Then, we add the index of the current element to the queue. At this point, the front element of the queue is the maximum value of the current sliding window. Note that we add the front element of the queue to the result array when the index i is greater than or equal to k-1.
The time complexity is O(n), and the space complexity is O(k). Here, n is the length of the array nums.
function maxSlidingWindow(nums: number[], k: number): number[] {
const ans: number[] = [];
const q = new Deque();
for (let i = 0; i < nums.length; ++i) {
if (!q.isEmpty() && i - q.front()! >= k) {
q.popFront();
}
while (!q.isEmpty() && nums[q.back()!] <= nums[i]) {
q.popBack();
}
q.pushBack(i);
if (i >= k - 1) {
ans.push(nums[q.front()!]);
}
}
return ans;
}func maxSlidingWindow(nums []int, k int) (ans []int) {
q := []int{}
for i, x := range nums {
if len(q) > 0 && i-q[0] >= k {
q = q[1:]
}
for len(q) > 0 && nums[q[len(q)-1]] <= x {
q = q[:len(q)-1]
}
q = append(q, i)
if i >= k-1 {
ans = append(ans, nums[q[0]])
}
}
return
}use std::collections::VecDeque;
impl Solution {
pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
let k = k as usize;
let mut ans = Vec::new();
let mut q: VecDeque<usize> = VecDeque::new();
for i in 0..nums.len() {
if let Some(&front) = q.front() {
if i >= front + k {
q.pop_front();
}
}
while let Some(&back) = q.back() {
if nums[back] <= nums[i] {
q.pop_back();
} else {
break;
}
}
q.push_back(i);
if i >= k - 1 {
ans.push(nums[*q.front().unwrap()]);
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force | Time complexity: O(n*k) |
| Approach 2: Optimized Deque Method | Time complexity: O(n) |
| Priority Queue (Max-Heap) | – |
| Monotonic Queue | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(nk) | O(1) | Good for small inputs or quickly validating logic during early problem exploration |
| Monotonic Deque (Sliding Window) | O(n) | O(k) | Best general solution for large arrays and the expected approach in coding interviews |
Frequently asked questions
Is Sliding Window Maximum easy or hard?
Sliding Window Maximum is typically classified as a hard problem because the optimal solution requires recognizing the monotonic queue pattern. Many developers first attempt heap or brute force approaches before learning the O(n) deque optimization.
How to solve Sliding Window Maximum in O(n)?
Maintain a deque that stores indices of elements in decreasing order of value. Remove indices that fall outside the current window and pop smaller elements from the back before inserting a new element. The front of the deque always represents the maximum for the current window.
Sliding Window Maximum Python or Java solution?
Most implementations use a deque from standard libraries such as collections.deque in Python or ArrayDeque/LinkedList in Java. The algorithm stores indices, removes outdated indices, and keeps the deque decreasing so the front always gives the window maximum.
What is the best approach for Sliding Window Maximum?
The optimal approach uses a monotonic deque that stores indices of elements in decreasing order of values. The maximum element of the current window is always at the front of the deque. Each element is inserted and removed at most once, giving O(n) time complexity and O(k) space complexity.
Is Sliding Window Maximum asked at Google/Amazon/Meta?
Sliding Window Maximum is a common interview problem at companies like Google, Amazon, and Meta because it tests sliding window techniques, queue behavior, and amortized analysis. Variations also appear in system design and streaming data problems.
What data structure is used in Sliding Window Maximum?
The optimal solution uses a double-ended queue (deque) that acts as a monotonic queue. This structure allows constant-time insertion and removal from both ends while maintaining candidates for the maximum element.
What is the time complexity of Sliding Window Maximum?
The brute force solution runs in O(nk) time because it recomputes the maximum for every window. The optimized monotonic deque approach runs in O(n) time since each element is processed once when added and once when removed from the deque.