Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Scanning each window for its maximum is O(n·k).
  2. 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);
    }
}

Solve Sliding Window Maximum online · All practice problems