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:
arr = [1, 3, 2, 5, 8, 7] k = 3
Output:
[3, 5, 8, 8]
Try it yourself
Explanation
Brute force
We can write a nested loop, the outer loop going through each window, and the inner loop finding the max within the window. This is O(N^2) time complexity.
To optimize beyond brute force, we can either reduce the complexity of the outer or inner loop. Since we must 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 the 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 is 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.
Max Heap
One way to achieve this goal is to push the window elements in a max heap and pop the leftmost element out of the heap when the window slides.
The time complexity of this approach is O(N log(k)) since we have to push k elements into the heap and pop k elements out of the heap for each window. The space complexity is O(k) since the heap can only hold k elements at a time.
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 space complexity is O(N) as there may be at most N elements in the deque.
The main reason the monotonic deque achieves this is that it stores both magnitude and position information. From head to tail, the elements get smaller and are 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 Deque, List
3
4def sliding_window_maximum(nums: List[int], k: int) -> List[int]:
5 q: Deque[int] = 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)))
251import 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}
421"use strict";
2
3function slidingWindowMaximum(nums, k) {
4 const q = []; // stores *indices*
5 const res = [];
6 for (let i = 0; i < nums.length; i++) {
7 while (q.length > 0 && nums[q[q.length - 1]] <= nums[i]) {
8 q.pop();
9 }
10 q.push(i);
11 // remove first element if it's outside the window
12 if (q[0] === i - k) {
13 q.shift();
14 }
15 // 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)
16 if (i >= k - 1) {
17 res.push(nums[q[0]]);
18 }
19 }
20 return res;
21}
22
23function splitWords(s) {
24 return s === "" ? [] : s.split(" ");
25}
26
27function* main() {
28 const nums = splitWords(yield).map((v) => parseInt(v));
29 const k = parseInt(yield);
30 const res = slidingWindowMaximum(nums, k);
31 console.log(res.join(" "));
32}
33
34class EOFError extends Error {}
35{
36 const gen = main();
37 const next = (line) => gen.next(line).done && process.exit();
38 let buf = "";
39 next();
40 process.stdin.setEncoding("utf8");
41 process.stdin.on("data", (data) => {
42 const lines = (buf + data).split("\n");
43 buf = lines.pop();
44 lines.forEach(next);
45 });
46 process.stdin.on("end", () => {
47 buf && next(buf);
48 gen.throw(new EOFError());
49 });
50}
511#include <algorithm>
2#include <deque>
3#include <iostream>
4#include <iterator>
5#include <limits>
6#include <sstream>
7#include <string>
8#include <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 ss >> std::boolalpha;
36 std::vector<T> v;
37 std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
38 return v;
39}
40
41void ignore_line() {
42 std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
43}
44
45template<typename T>
46void put_words(const std::vector<T>& v) {
47 if (!v.empty()) {
48 std::copy(v.begin(), std::prev(v.end()), std::ostream_iterator<T>{std::cout, " "});
49 std::cout << v.back();
50 }
51 std::cout << '\n';
52}
53
54int main() {
55 std::vector<int> nums = get_words<int>();
56 int k;
57 std::cin >> k;
58 ignore_line();
59 std::vector<int> res = sliding_window_maximum(nums, k);
60 put_words(res);
61}
62