Practice › Sliding Window
Sliding Window Maximum
Hard · Sliding Window · Asked at Amazon, Google, Microsoft, Flipkart
For every window of size k, print the maximum element.
Input
First line: n. Second line: n integers. Third line: k.
Output
n − k + 1 numbers, space-separated.
Constraints
- 1 ≤ k ≤ n ≤ 10^5
- -10^4 ≤ a[i] ≤ 10^4
A monotonic deque gives O(n) overall.
Example 1
Input
8 1 3 -1 -3 5 3 6 7 3
Output
3 3 5 5 6 7
Example 2
Input
1 1 1
Output
1
Hints
- Scanning each window for its maximum is O(n·k).
- Keep a deque of indices whose values are decreasing. The front is the window's maximum; pop from the back anything smaller than the new element.
Approach
A monotonic deque stores indices of possible maxima, with values in decreasing order. For each i: drop the front if it has left the window (front <= i − k). Pop from the back every index whose value is ≤ a[i], since those can never be a maximum again. Push i. Once i ≥ k − 1, a[front] is the window maximum. Every index is pushed and popped at most once, so the total is O(n).
Complexity: O(n) time · O(k) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
cin >> k;
deque<int> dq;
for (int i = 0; i < n; i++) {
if (!dq.empty() && dq.front() <= i - k) dq.pop_front();
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
dq.push_back(i);
if (i >= k - 1) cout << a[dq.front()] << (i + 1 < n ? " " : "\n");
}
return 0;
}Python solution
import sys
from collections import deque
data = list(map(int, sys.stdin.read().split()))
n = data[0]
a, k = data[1 : n + 1], data[n + 1]
dq, out = deque(), []
for i, x in enumerate(a):
if dq and dq[0] <= i - k:
dq.popleft()
while dq and a[dq[-1]] <= x:
dq.pop()
dq.append(i)
if i >= k - 1:
out.append(a[dq[0]])
print(*out)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
int k = sc.nextInt();
ArrayDeque<Integer> dq = new ArrayDeque<>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();
dq.addLast(i);
if (i >= k - 1) sb.append(sb.length() > 0 ? " " : "").append(a[dq.peekFirst()]);
}
System.out.println(sb);
}
}