.png)
Sliding Window Maximum
Problem Statement
You are given an integer array arr of size n and an integer k.
For each contiguous subarray (window) of size k, find the maximum element in that window.
Example
Input
arr = [1,3,-1,-3,5,3,6,7]
k = 3
Output
[3, 3, 5, 5, 6, 7]
Why This Problem Is Important
Very common interview problem
Tests sliding window optimization
Introduces deque (monotonic queue) concept
Used in time-series, stock, and streaming problems
Foundation for window-based max/min problems
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(n × k) | O(1) |
| Approach 2 | Max Heap | O(n log k) | O(k) |
| Approach 3 | Deque (Monotonic Queue) | O(n) | O(k) |
Approach 1: Brute Force
Idea
For every window of size k, scan all elements and find the maximum.
Algorithm
- Loop from i = 0 to n - k
- Initialize max
- Scan elements from i to i + k - 1
- Store maximum
Time & Space Complexity
Time: O(n × k)
Space: O(1)
C Implementation
#include
int main() {
int arr[] = {1,3,-1,-3,5,3,6,7};
int n = 8, k = 3;
for(int i = 0; i <= n - k; i++) {
int max = arr[i];
for(int j = i; j < i + k; j++) {
if(arr[j] > max)
max = arr[j];
}
printf("%d ", max);
}
return 0;
}
Output:
3 3 5 5 6 7
C++ Implementation
#include
using namespace std;
int main() {
int arr[] = {1,3,-1,-3,5,3,6,7};
int n = 8, k = 3;
for(int i = 0; i <= n - k; i++) {
int mx = arr[i];
for(int j = i; j < i + k; j++)
mx = max(mx, arr[j]);
cout << mx << " ";
}
return 0;
}
Output:
3 3 5 5 6 7
Java Implementation
public class Main {
public static void main(String[] args) {
int[] arr = {1,3,-1,-3,5,3,6,7};
int k = 3;
for(int i = 0; i <= arr.length - k; i++) {
int max = arr[i];
for(int j = i; j < i + k; j++)
max = Math.max(max, arr[j]);
System.out.print(max + " ");
}
}
}
Output:
3 3 5 5 6 7
Python Implementation
arr = [1,3,-1,-3,5,3,6,7]
k = 3
for i in range(len(arr) - k + 1):
print(max(arr[i:i+k]), end=" ")
Output:
3 3 5 5 6 7
JavaScript Implementation
let arr = [1,3,-1,-3,5,3,6,7];
let k = 3;
for(let i = 0; i <= arr.length - k; i++) {
let max = arr[i];
for(let j = i; j < i + k; j++)
max = Math.max(max, arr[j]);
process.stdout.write(max + " ");
}
Output:
3 3 5 5 6 7
C# Implementation
using System;
class Program {
static void Main() {
int[] arr = {1,3,-1,-3,5,3,6,7};
int k = 3;
for(int i = 0; i <= arr.Length - k; i++) {
int max = arr[i];
for(int j = i; j < i + k; j++)
max = Math.Max(max, arr[j]);
Console.Write(max + " ");
}
}
}
Output:
3 3 5 5 6 7
Approach 2: Max Heap
Idea
Use a max heap to always get the maximum in the current window.
Algorithm
- Push elements into heap with index
- Remove elements outside the window
- Top of heap is the maximum
Time & Space Complexity
Time: O(n log k)
Space: O(k)
C Implementation (Manual Max Heap)
#include
#define MAXN 1000
typedef struct {
int val;
int idx;
} Node;
Node heap[MAXN];
int size = 0;
void swap(Node *a, Node *b) {
Node temp = *a;
*a = *b;
*b = temp;
}
void push(Node x) {
heap[size] = x;
int i = size++;
while (i > 0 && heap[(i-1)/2].val < heap[i].val) {
swap(&heap[i], &heap[(i-1)/2]);
i = (i-1)/2;
}
}
void pop() {
heap[0] = heap[--size];
int i = 0;
while (1) {
int largest = i;
int l = 2*i+1, r = 2*i+2;
if (l < size && heap[l].val > heap[largest].val) largest = l;
if (r < size && heap[r].val > heap[largest].val) largest = r;
if (largest == i) break;
swap(&heap[i], &heap[largest]);
i = largest;
}
}
Node top() {
return heap[0];
}
int main() {
int arr[] = {1,3,-1,-3,5,3,6,7};
int n = 8, k = 3;
for (int i = 0; i < n; i++) {
push((Node){arr[i], i});
if (i >= k - 1) {
while (top().idx <= i - k)
pop();
printf("%d ", top().val);
}
}
return 0;
}
C++ Implementation
#include
#include
using namespace std;
int main() {
int arr[] = {1,3,-1,-3,5,3,6,7};
int n = 8, k = 3;
priority_queue> pq;
for(int i = 0; i < n; i++) {
pq.push({arr[i], i});
if(i >= k - 1) {
while(pq.top().second <= i - k)
pq.pop();
cout << pq.top().first << " ";
}
}
return 0;
}
Java Implementation
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
int[] arr = {1,3,-1,-3,5,3,6,7};
int k = 3;
PriorityQueue pq = new PriorityQueue<>(
(a, b) -> b[0] - a[0]
);
for(int i = 0; i < arr.length; i++) {
pq.add(new int[]{arr[i], i});
if(i >= k - 1) {
while(pq.peek()[1] <= i - k)
pq.poll();
System.out.print(pq.peek()[0] + " ");
}
}
}
}
Python Implementation
import heapq
arr = [1,3,-1,-3,5,3,6,7]
k = 3
heap = []
for i in range(len(arr)):
heapq.heappush(heap, (-arr[i], i))
if i >= k - 1:
while heap[0][1] <= i - k:
heapq.heappop(heap)
print(-heap[0][0], end=" ")
JavaScript Implementation (Custom Max Heap)
class MaxHeap {
constructor() {
this.heap = [];
}
push(val, idx) {
this.heap.push([val, idx]);
this.bubbleUp();
}
bubbleUp() {
let i = this.heap.length - 1;
while (i > 0) {
let p = Math.floor((i - 1) / 2);
if (this.heap[p][0] >= this.heap[i][0]) break;
[this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
i = p;
}
}
pop() {
if (this.heap.length === 1) return this.heap.pop();
const top = this.heap[0];
this.heap[0] = this.heap.pop();
this.bubbleDown(0);
return top;
}
bubbleDown(i) {
const n = this.heap.length;
while (true) {
let largest = i;
let l = 2*i+1, r = 2*i+2;
if (l < n && this.heap[l][0] > this.heap[largest][0]) largest = l;
if (r < n && this.heap[r][0] > this.heap[largest][0]) largest = r;
if (largest === i) break;
[this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
i = largest;
}
}
top() { return this.heap[0]; }
}
let arr = [1,3,-1,-3,5,3,6,7];
let k = 3;
let heap = new MaxHeap();
for (let i = 0; i < arr.length; i++) {
heap.push(arr[i], i);
if (i >= k - 1) {
while (heap.top()[1] <= i - k)
heap.pop();
process.stdout.write(heap.top()[0] + " ");
}
}
C# Implementation
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr = {1,3,-1,-3,5,3,6,7};
int k = 3;
var pq = new PriorityQueue<(int val, int idx), int>();
for(int i = 0; i < arr.Length; i++) {
pq.Enqueue((arr[i], i), -arr[i]);
if(i >= k - 1) {
while(pq.Peek().idx <= i - k)
pq.Dequeue();
Console.Write(pq.Peek().val + " ");
}
}
}
}
Output (for all heap-based implementations)
For:
arr = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
The sliding window maximums are:
3 3 5 5 6 7
Approach 3: Deque (Optimal)
Idea
Maintain a monotonic decreasing deque:
- Front always holds the maximum
- Remove smaller elements from back
Algorithm
- Remove indices outside window
- Remove smaller elements from back
- Insert current index
- Front gives maximum
Time & Space Complexity
Time: O(n)
Space: O(k)
C++ Implementation
#include
#include
using namespace std;
int main() {
int arr[] = {1,3,-1,-3,5,3,6,7};
int n = 8, k = 3;
deque dq;
for(int i = 0; i < n; i++) {
if(!dq.empty() && dq.front() == i - k)
dq.pop_front();
while(!dq.empty() && arr[dq.back()] < arr[i])
dq.pop_back();
dq.push_back(i);
if(i >= k - 1)
cout << arr[dq.front()] << " ";
}
return 0;
}
Java Implementation
import java.util.Deque;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
int[] arr = {1,3,-1,-3,5,3,6,7};
int k = 3;
Deque dq = new LinkedList<>();
for(int i = 0; i < arr.length; i++) {
if(!dq.isEmpty() && dq.peekFirst() == i - k)
dq.pollFirst();
while(!dq.isEmpty() && arr[dq.peekLast()] < arr[i])
dq.pollLast();
dq.addLast(i);
if(i >= k - 1)
System.out.print(arr[dq.peekFirst()] + " ");
}
}
}
Python Implementation
from collections import deque
arr = [1,3,-1,-3,5,3,6,7]
k = 3
dq = deque()
for i in range(len(arr)):
if dq and dq[0] == i - k:
dq.popleft()
while dq and arr[dq[-1]] < arr[i]:
dq.pop()
dq.append(i)
if i >= k - 1:
print(arr[dq[0]], end=" ")
JavaScript Implementation
let arr = [1,3,-1,-3,5,3,6,7];
let k = 3;
let dq = [];
for(let i = 0; i < arr.length; i++) {
if(dq.length && dq[0] === i - k)
dq.shift();
while(dq.length && arr[dq[dq.length - 1]] < arr[i])
dq.pop();
dq.push(i);
if(i >= k - 1)
process.stdout.write(arr[dq[0]] + " ");
}
C# Implementation
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr = {1,3,-1,-3,5,3,6,7};
int k = 3;
LinkedList dq = new LinkedList();
for(int i = 0; i < arr.Length; i++) {
if(dq.Count > 0 && dq.First.Value == i - k)
dq.RemoveFirst();
while(dq.Count > 0 && arr[dq.Last.Value] < arr[i])
dq.RemoveLast();
dq.AddLast(i);
if(i >= k - 1)
Console.Write(arr[dq.First.Value] + " ");
}
}
}
Output:
3 3 5 5 6 7
Summary
- Brute force is simple but slow
- Heap improves but still not optimal
- Deque solution is interview-preferred
- Deque gives O(n) time using monotonic queue
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
