Question

LeetCode Link | 239. Sliding Window Maximum | Hard

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window. (The max value in that window)

Constrains

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 1 <= k <= nums.length

Examples

Example 1

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

Example 2

Input: nums = [1], k = 1
Output: [1]

Solution Approach

Method: Monotonic Queue

Constrains

  • None

This method does not have any limitations.

Concept Explanation

This is a classic problem for using a monotonic queue.

Using a brute force approach, you would iterate through the array and find the maximum value within the window each time, which would obviously result in an O(n × k) time complexity algorithm.

Why use a mono queue?

Some might consider using a max heap (priority queue) to store the k numbers within the window, allowing easy access to the largest value. However, the issue arises because the window is sliding, and while a max heap can efficiently remove the largest value, it cannot remove other values at arbitrary positions. This mismatch means the max heap does not maintain the correct set of numbers within the sliding window, making it unsuitable for this purpose.

At this point, what’s needed is a queue that can dynamically adjust as elements enter and exit the sliding window. This queue should be able to tell us the maximum value inside it after each move. This is where a monotonic queue comes into play, efficiently maintaining the desired properties as the window slides across the dataset.

By using a monotonic queue, we don’t need to maintain all the elements within the window; we only need to keep the elements that could potentially be the maximum value within the window. At the same time, we ensure that the elements in the queue are in descending order.

Let’s see how a monotonic queue maintains elements.

For window elements {2, 3, 5, 1, 4}, the monotonic queue only needs to maintain {5, 4}, ensuring the elements in the monotonic queue are in descending order. At this point, the front element of the queue is the maximum element within the window.

You might wonder how the monotonic queue maintaining {5, 4} works with the sliding window.

When designing the monotonic queue, the pop and push operations should follow these rules:

  • pop(value): If the element value being removed from the window equals the front element of the monotonic queue, then dequeue the element; otherwise, do nothing.
  • push(value): If the element value being pushed is greater than the value of the back element in the queue, continue dequeuing the back element until the value being pushed is less than or equal to the value of the back element.

By following these rules, each time the window moves, you only need to check que.front() to return the current maximum value of the window.

What data structure do we use to implement Monotonic queue?

Ans: Duque (Double-end Queue), for more detail, check the post Deque & Monotonic Queue.

Code

  • Time complexity: O(n)
  • Space complexity: O(k)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
function maxSlidingWindow(nums: number[], k: number): number[] {
	class MonoQueue {
		private readonly queue: number[];

		constructor() {
			this.queue = [];
		}

		// Enqueue in non-decrease order, this makes sure the top is the max value
		public enqueue(num: number): void {
			let bottom: number | undefined = this.queue[this.queue.length - 1];
			// Remove a tail element if smaller than the number to enqueue
			while (bottom !== undefined && bottom < num) {
				this.queue.pop();
				bottom = this.queue[this.queue.length - 1];
			}
			this.queue.push(num);
		}

		// Only remove if this is the max value in the last window, 
		// otherwise it has already been removed during an enqueue process
		public dequeue(num: number): void {
			if (num === this.top()) {
				this.queue.shift();
			}
		}

		public top(): number | undefined {
			return this.queue[0];
		}
	}

	const res: number[] = [];
	const queue: MonoQueue = new MonoQueue();
	let left: number = 0, right: number = 0;

	// Add init window (index [0, k - 1])
	while (right < k) {
		queue.enqueue(nums[right]);
		right++;
	}
	res.push(queue.top()!);

	// Sliding window
	while (right < nums.length) {
		queue.enqueue(nums[right]);
		queue.dequeue(nums[left]);
		res.push(queue.top()!);
		left++, right++;
	}

	return res;
};

Conclusion

It’s important to clarify that the pop and push interfaces for the monotonic queue in this solution are specifically tailored for this problem.

Monotonic queues are not rigidly fixed! They can vary in implementation depending on the scenario. The key is to maintain the principle of monotonicity, either decreasing or increasing, which is why it’s called a monotonic queue. Don’t assume that the implementation of the monotonic queue in this problem is a fixed method.