Sliding Window Maximum

June 4, 2025

Introduction to Sliding window maximum

Let‘s keep things simple. Suppose you‘re following the stock prices minute by minute and want to find the highest price in each 5-minute window. You move the window over one minute and repeat.

That‘s what the Sliding Window Maximum problem is all about—determining the maximum element in each subarray (or window) of size k as it traverses the array.

Let’s keep things simple. Suppose you’re following the stock prices minute by minute and want to find the highest price in each 5-minute window. You move the window over one minute and repeat.

That’s what the Sliding Window Maximum problem is all about determining the maximum element in each subarray (or window) of size k as it traverses the array.

What is Sliding Window Maximum?

A sliding window is a moving frame of length k over an array or dataset. It aids in cutting down on unnecessary calculations.

Imagine this: You have a moving magnifying glass over text, and you look only at words under the lens (the current window) at any point in time.

Use Cases

Finding averages
Maximum/minimum values
Distinct elements
Pattern matching

Different Approaches to Solve It:

1. Naive Approach (O(n × k))

Loop through each window of size k, scan its elements to find the max.

Easy but inefficient for large inputs.

2. Max-Heap / Priority Queue Approach (O(n log n))

Use a max-heap to keep track of the largest element in the window.

Better than brute-force, but slightly more overhead.

3. Deque Approach (Optimal O(n))

Use a double-ended queue to store indices of useful elements and discard those that are out of the window or smaller than the current number.

Best and most used in interviews and production.

Algorithm for Sliding Window

Initialize the Window
Set the starting window of size k on the first k elements.
Process the Current Window
Find the maximum value in the current window.
Move the Window
Slide the window by one position:
- Add the new (next) element.
- Remove the oldest element (which is now outside the window).
Repeat
Continue steps 2–3 until the window reaches the end of the array.
Return/Print the List of Maximums

Sliding Window Maximum Subarray using Naive Approach

The Naive Approach to solving the Sliding window problem is simple but inefficient for large arrays. It involves brute-force scanning each window to find the maximum.

Here’s a simple Python program demonstrating the naive approach:

Problem Statement:

Given an array arr[] of size n and an integer k, find the maximum for each contiguous subarray of size k.

Algorithm:

Loop through the array from index i = 0 to n - k.
For each window of size k starting at index i, find the maximum element by scanning all k elements.
Store or print this maximum.

				
					def max_sliding_window_naive(arr, k):
    n = len(arr)
    result = []
    for i in range(n - k + 1):
        max_val = arr[i]
        for j in range(1, k):
            max_val = max(max_val, arr[i + j])
        result.append(max_val)
    return result

Input :

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

Output:

				
					[3, 3, 7, 7]

Explanation :

Window [1, 3, 2] → max = 3
Window [3, 2, 1] → max = 3
Window [2, 1, 7] → max = 7
Window [1, 7, 3] → max = 7

Time Complexity:

O(n × k) → For each of the (n - k + 1) windows, we scan k elements.

Space Complexity:

O(1) (excluding the result list).

Sliding Window Maximum Subarray using Using Max-Heap (Priority Queue)

This approach uses a max-heap (priority queue) to efficiently retrieve the maximum element in each window. We store tuples of (-value, index) to simulate a max-heap in Python using heapq (which is a min-heap by default).

How It Works

Push the first k elements into the heap.
For each new element, remove the ones that are outside the current window.
The root of the heap is always the current max.
Push the new max to the result list.

				
					import heapq

def sliding_window_max_heap(nums, k):
    heap = []
    result = []

    for i in range(len(nums)):
        heapq.heappush(heap, (-nums[i], i))

        while heap and heap[0][1] <= i - k:
            heapq.heappop(heap)

        if i >= k - 1:
            result.append(-heap[0][0])

    return result

Output :

[3, 3, 5, 5, 6, 7]

Time and Space Complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

Pros

Handles dynamic data streams well
Easier to adapt for k-th largest or variable-sized windows

Cons

Slightly slower due to log(n) heap operations
More complex than deque solution

Sliding Window Maximum Using Deque (Optimal Solution)

The deque (double-ended queue) method is the most optimal and preferred solution. It maintains a list of indices for potential max values in each window.

How It Works

Use deque to store indices in a monotonic decreasing order of values.
Remove elements from the back of the deque if they are smaller than the current element.
Remove elements from the front if they are outside the window range.
Append the deque’s front value (max) to the result for every window.

				
					from collections import deque

def sliding_window_max_deque(nums, k):
    dq = deque()
    result = []

    for i in range(len(nums)):
        if dq and dq[0] == i - k:
            dq.popleft()

        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

Time and Space Complexity

Time Complexity: O(n)
Space Complexity: O(k)

Pros

Most efficient solution for large inputs
Used in real-world applications and coding interviews

Cons

Requires understanding deque operations
Slightly more logic-heavy to implement correctly

Output :

[3, 3, 5, 5, 6, 7]

Applications

Stock Market – Track price trends
IoT Devices – Real-time sensor data analysis
Streaming Services – Buffer and bitrate optimizations
Cybersecurity – Monitor peak network traffic

Sliding Window Maximum in Other Problems

Minimum in sliding window
First negative integer in every window
Number of distinct elements in every window of size k

These problems follow a very similar pattern. Once you master max, the rest fall in line like dominos.

Sliding Window Maximum in Interviews

Common Interview Questions: LeetCode 239: Sliding Window Maximum

PrepInsta: Top 100 Codes

To wrap it up:

The Sliding Window Maximum is more than just a coding challenge—it’s a real-world solution for time-sensitive data. Mastering this pattern will not only help in interviews but also in practical applications from finance to tech infrastructure.

Frequently Asked Questions

Is this problem commonly asked in coding interviews?

Yes, it is a frequent interview question in top tech companies like Google, Microsoft, and Amazon. Variants of this problem also appear in platforms like LeetCode (Problem 239), PrepInsta Prime

What is the difference between the sliding window maximum and minimum techniques?

The sliding window maximum finds the largest value in each window, while the sliding window minimum finds the smallest. The logic is similar, but the condition inside the deque operations is inverted.

Can I implement this sliding window technique in Python, Java, and C++?

Yes, you can implement the sliding window maximum algorithm in any programming language. Python uses collections.deque, Java uses LinkedList or Deque, and C++ uses std::deque.

What are the top LeetCode problems similar to this sliding window technique?

Some top LeetCode problems similar to Sliding Window Maximum are:

239. Sliding Window Maximum
480. Sliding Window Median
First Negative Integer in Every Window of Size K
Count of Distinct Elements in Every Window

Learn DSA

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Unlock this article for Free, by logging in

Sliding Window Maximum

Introduction to Sliding window maximum

Introduction to Sliding window maximum

What is Sliding Window Maximum?

Use Cases

Different Approaches to Solve It:

Different Approaches to Solve It:

1. Naive Approach (O(n × k))

2. Max-Heap / Priority Queue Approach (O(n log n))

3. Deque Approach (Optimal O(n))

Algorithm for Sliding Window

Sliding Window Maximum Subarray using Naive Approach

Problem Statement:

Algorithm:

Input :

Output:

Explanation :

Sliding Window Maximum Subarray using Using Max-Heap (Priority Queue)

How It Works

Output :

Time and Space Complexity

Pros

Cons

Sliding Window Maximum Using Deque (Optimal Solution)

How It Works

Time and Space Complexity

Pros

Cons

Output :

Applications

Sliding Window Maximum in Other Problems

To wrap it up:

Frequently Asked Questions

Learn DSA

Prime Course Trailer

Related Banners

Get over 200+ course One Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

30+ Companies are Hiring

Unlock this article for Free,
by logging in