Find every sliding-window maximum
Return the maximum value in every contiguous window of a fixed size as it moves across an integer array.
Course progress
Problem 89 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
numbers = [1,3,-1,-3,5,3,6,7]; window = 3
Expected output
3 3 5 5 6 7
What is happening?
The six windows have maximums 3, 3, 5, 5, 6, and 7 respectively. A decreasing deque keeps only candidates that can still become a maximum.
Solution strategy
Build the right mental model
Keep candidate indexes in decreasing value order. Remove expired indexes from the front and weaker candidates from the back.
Core concepts
deque · sliding window
Complexity
Time O(n), space O(window size).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for sliding-window-maximum
using System;
using System.Collections.Generic;
class Program
{
static List<int> WindowMaximums(int[] numbers, int size)
{
if (size < 1 || size > numbers.Length) throw new ArgumentOutOfRangeException("size");
var candidates = new LinkedList<int>();
var result = new List<int>();
for (int index = 0; index < numbers.Length; index++)
{
while (candidates.Count > 0 && candidates.First.Value <= index - size)
candidates.RemoveFirst();
while (candidates.Count > 0 && numbers[candidates.Last.Value] <= numbers[index])
candidates.RemoveLast();
candidates.AddLast(index);
if (index >= size - 1) result.Add(numbers[candidates.First.Value]);
}
return result;
}
static void Main()
{
Console.WriteLine(string.Join(" ", WindowMaximums(
new[] { 1, 3, -1, -3, 5, 3, 6, 7 }, 3)));
}
}Knowledge check
Questions students often ask
What is the main idea behind find every sliding-window maximum?
Keep candidate indexes in decreasing value order. Remove expired indexes from the front and weaker candidates from the back.
What is the time and space complexity of this solution?
Time O(n), space O(window size).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.