Sliding Window Maximum | Monotonic Stack

We have an array and a sliding window defined by a start index and an end index. The sliding window moves from left of the array to right. There are always k elements in the window. The window moves one position at a time. Find the maximum integer within the window each time it moves.

Input:

1arr = [1, 3, 2, 5, 8, 7]
2k = 3

Output:

1[3, 5, 8, 8]

Try it yourself

Explanation

Brute force

We can write a nested loop, the outer loop goes through each window and the inner loop finds the max within the window. This is O(N^2) time complexity.

To optimize on brute force, we can either reduce outer or inner loop complexity. Since we have to examine each element at least once (there's no way to find the maximum if we don't know what the values are..), there is not much we can do for outer loop. So we have to work on the inner loop.

Preserving the maximum of elements in the window

Currently, to get the max of the sliding window, we look at each element in the window and compare them. Analogous to sliding window sum problem (given an array and a window size, return the sum of each window), when a window slides, only two elements change - the leftmost gets removed and a new element gets added to the right. Everything in the middle (let's call them "window elements") is unchanged, and the maximum element among these window elements are unchanged as well. The key to reducing inner loop complexity is to persist the maximum of the window elements as we slide the window. Ideally, we want to be able to access the maximum element in less than O(N) time and updating it in less than O(N) time.

Balanced binary search tree

One way to achieve this goal is to save the window elements in a self-balancing binary search tree. Because it's self-balancing, the depth of the tree is guaranteed to be O(log(N)) so lookup, getting max, insert and delete are all O(log(N)) operations. Every time we slide the window, we remove the node that's out of the window and add the one that comes into the window to the tree. Overall, this gives us O(N log(k)) since the number of tree nodes is k and we slide max N times.

This is pretty good already, but can we do better?

Larger elements entering the window invalidates smaller elements

A question we can ask ourselves is "do we need to keep all the window elements in our state?". An important observation is for two elements arr[left] and arr[right], where left < right, arr[left] leaves the window earlier as we slide. If arr[right] is larger than arr[left], then there is no point keeping arr[left] in our state since arr[right] is always gonna be larger during the time arr[left] is in the window. Therefore, arr[left] can never be the maximum.

Monotonic deque

Here we introduce an interesting data structure. It's a deque with an interesting property - the elements in the deque from head to tail are in decreasing order (hence the name monotonic).

To achieve this property, we modify the push operation so that

when we push an element into the deque, we first pop everything smaller than it out of the deque.

This enforces the decreasing order. Let's see it in action.

The time complexity is O(N). This is because each element in the original array can only be pushed into and popped out of the deque once.

The main reason the monotonic deque can achieve this is it stores both magnitude and position information. From head to tail, the elements get smaller and further to the right of the array.

Implementation

In the actual implementation, we store indices instead of actual elements in the deque. This is because we need the index to know if an element is out of the window or not and we can always get the value using the index from the array.

1from collections import deque
2from typing import List
3
4def sliding_window_maximum(nums: List[int], k: int) -> List[int]:
5    q = deque() # stores *indices*
6    res = []
7    for i, cur in enumerate(nums):
8        while q and nums[q[-1]] <= cur:
9            q.pop()
10        q.append(i)
11        # remove first element if it's outside the window
12        if q[0] == i - k:
13            q.popleft()
14        # if window has k elements add to results (first k-1 windows have < k elements because we start from empty window and add 1 element each iteration)
15        if i >= k - 1:
16            res.append(nums[q[0]])
17
18    return res
19
20if __name__ == '__main__':
21    nums = [int(x) for x in input().split()]
22    k = int(input())
23    res = sliding_window_maximum(nums, k)
24    print(' '.join(map(str, res)))
25
1import java.util.ArrayDeque;
2import java.util.ArrayList;
3import java.util.Arrays;
4import java.util.List;
5import java.util.Scanner;
6import java.util.stream.Collectors;
7
8class Solution {
9    public static List<Integer> slidingWindowMaximum(List<Integer> nums, int k) {
10        ArrayDeque<Integer> q = new ArrayDeque<>(k);  // stores *indices*
11        ArrayList<Integer> res = new ArrayList<>();
12        for (int i = 0; i < nums.size(); i++) {
13            while (!q.isEmpty() && nums.get(q.getLast()) <= nums.get(i)) {
14                q.removeLast();
15            }
16            q.addLast(i);
17            // remove first element if it's outside the window
18            if (q.getFirst() == i - k) {
19                q.removeFirst();
20            }
21            // if window has k elements add to results (first k-1 windows have < k elements because we start from empty window and add 1 element each iteration)
22            if (i >= k - 1) {
23                res.add(nums.get(q.getFirst()));
24            }
25        }
26        return res;
27    }
28
29    public static List<String> splitWords(String s) {
30        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
31    }
32
33    public static void main(String[] args) {
34        Scanner scanner = new Scanner(System.in);
35        List<Integer> nums = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
36        int k = Integer.parseInt(scanner.nextLine());
37        scanner.close();
38        List<Integer> res = slidingWindowMaximum(nums, k);
39        System.out.println(res.stream().map(String::valueOf).collect(Collectors.joining(" ")));
40    }
41}
42
1function slidingWindowMaximum(nums, k) {
2    const q = [];  // stores *indices*
3    const res = [];
4    for (let i = 0; i < nums.length; i++) {
5        while (q && nums[q[q.length - 1]] <= nums[i]) {
6            q.pop();
7        }
8        q.push(i);
9        // remove first element if it's outside the window
10        if (q[0] === i - k) {
11            q.shift();
12        }
13        // if window has k elements add to results (first k-1 windows have < k elements because we start from empty window and add 1 element each iteration)
14        if (i >= k - 1) {
15            res.push(nums[q[0]]);
16        }
17    }
18    return res;
19}
20
21function splitWords(s) {
22    return s == "" ? [] : s.split(' ');
23}
24
25function* main() {
26    const nums = splitWords(yield).map((v) => parseInt(v));
27    const k = parseInt(yield);
28    const res = slidingWindowMaximum(nums, k);
29    console.log(res.join(' '));
30}
31
32class EOFError extends Error {}
33{
34    const gen = main();
35    const next = (line) => gen.next(line).done && process.exit();
36    let buf = '';
37    next();
38    process.stdin.setEncoding('utf8');
39    process.stdin.on('data', (data) => {
40        const lines = (buf + data).split('\n');
41        buf = lines.pop();
42        lines.forEach(next);
43    });
44    process.stdin.on('end', () => {
45        buf && next(buf);
46        gen.throw(new EOFError());
47    });
48}
49
1#include <algorithm> // copy
2#include <deque> // deque
3#include <iostream> // cin, cout, streamsize
4#include <iterator> // back_inserter, istream_iterator, ostream_iterator, prev
5#include <limits> // numeric_limits
6#include <sstream> // istringstream
7#include <string> // getline, string
8#include <vector> // vector
9
10std::vector<int> sliding_window_maximum(std::vector<int> nums, int k) {
11    std::deque<int> max_indices;
12    std::vector<int> res;
13    for (int i = 0; i < nums.size(); i++) {
14        while (!max_indices.empty() && nums[max_indices.back()] <= nums[i]) {
15            max_indices.pop_back();
16        }
17        max_indices.push_back(i);
18        // remove first element if it's outside the window
19        if (max_indices.front() == i - k) {
20            max_indices.pop_front();
21        }
22        // if window has k elements add to results (first k-1 windows have < k elements because we start from empty window and add 1 element each iteration)
23        if (i >= k - 1) {
24            res.emplace_back(nums[max_indices.front()]);
25        }
26    }
27    return res;
28}
29
30template<typename T>
31std::vector<T> get_words() {
32    std::string line;
33    std::getline(std::cin, line);
34    std::istringstream ss{line};
35    std::vector<T> v;
36    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
37    return v;
38}
39
40void ignore_line() {
41    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
42}
43
44template<typename T>
45void put_words(const std::vector<T>& v) {
46    if (!v.empty()) {
47        std::copy(v.begin(), std::prev(v.end()), std::ostream_iterator<T>{std::cout, " "});
48        std::cout << v.back();
49    }
50    std::cout << '\n';
51}
52
53int main() {
54    std::vector<int> nums = get_words<int>();
55    int k;
56    std::cin >> k;
57    ignore_line();
58    std::vector<int> res = sliding_window_maximum(nums, k);
59    put_words(res);
60}
61