Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Find Maximum in Sliding Window

Explore how to efficiently find the maximum value in each sliding window of an integer array using a deque. Understand the step-by-step approach with examples, the logic behind maintaining a decreasing order in the deque, and how this method achieves optimal time and space complexity. This lesson helps you implement and analyze this common problem relevant to stacks and queues.

We'll cover the following...

Statement

Given an integer array and a window of size w, find the current maximum value in the window as it slides through the entire array.

Note: If the window size is greater than the array size, we will consider the entire array as a single window.

Example

Sample input

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
window_size = 3

Expected output

[3, 4, 5, 6, 7, 8, 9, 10]

Try it yourself #

#include <iostream>
#include <vector>
using namespace std;
vector<int> FindMaxSlidingWindow(vector<int>& nums, int window_size) {
	// Write your code
	vector<int> result;
	return result;
}

Solution

The algorithm uses the deque data structure to find the maximum in a window. A deque is a double-ended queue where the push and pop operations work in O ...