Sliding Window Maximum – Tech Interview Dot Org

💡Strategies for Solving This Problem

Understanding Sliding Window Maximum

Given an array and a window size k, find the maximum value in each window as it slides from left to right. This is a classic problem testing understanding of deques and optimization techniques.

Problem Statement

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3

Output: [3,3,5,5,6,7]

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

Naive Approach: O(nk)

For each window, scan all k elements to find max. Too slow for large inputs.


def max_sliding_window_naive(nums, k):
    result = []
    for i in range(len(nums) - k + 1):
        window_max = max(nums[i:i+k])
        result.append(window_max)
    return result
# Time: O(n*k), Space: O(1)

Better Approach: Max Heap - O(n log k)

Use max heap to track window maximum. Remove old elements as window slides.

Issue: Heap doesn't support efficient removal of arbitrary elements. Need to track indices.

Optimal: Monotonic Deque - O(n)

Key Insight: If element A enters before element B, and A ≤ B, then A can never be the maximum while B is in the window.

Strategy:

Maintain deque of indices in decreasing order of values
Front of deque always holds index of current maximum
Remove indices outside current window
Remove indices with smaller values than current element (they can't be max)

Why Deque?

O(1) access to both ends
Can remove from both front (old elements) and back (smaller elements)
Perfect for maintaining order while sliding

Asked at: Amazon, Google, Microsoft, Facebook, Bloomberg

✅Solution

Solution: Monotonic Deque - O(n)


from collections import deque

def max_sliding_window(nums, k):
    """
    Find maximum in each sliding window of size k

    Args:
        nums: List of integers
        k: Window size

    Returns:
        List of maximums for each window

    Time: O(n) - each element added and removed at most once
    Space: O(k) - deque stores at most k elements
    """
    if not nums or k == 0:
        return []

    if k == 1:
        return nums

    dq = deque()  # Stores indices
    result = []

    for i in range(len(nums)):
        # Remove indices outside current window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove indices with smaller values than current
        # (they can't be maximum while current is in window)
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        # Add current index
        dq.append(i)

        # Window is complete when i >= k-1
        if i >= k - 1:
            result.append(nums[dq[0]])  # Front has max index

    return result

# Test
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# Output: [3, 3, 5, 5, 6, 7]

print(max_sliding_window([1,-1], 1))
# Output: [1, -1]

print(max_sliding_window([9,11], 2))
# Output: [11]

Step-by-Step Example

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

i=0: nums[0]=1
  deque: [0] (index 0)

i=1: nums[1]=3
  3 > 1, remove index 0
  deque: [1]

i=2: nums[2]=-1
  -1 < 3, keep all
  deque: [1, 2]
  Window complete! Max = nums[1] = 3

i=3: nums[3]=-3
  Remove index 0 (outside window)
  -3 < -1, keep all
  deque: [1, 2, 3]
  Max = nums[1] = 3

i=4: nums[4]=5
  5 > all, clear deque
  deque: [4]
  Max = nums[4] = 5

i=5: nums[5]=3
  3 < 5, keep all
  deque: [4, 5]
  Max = nums[4] = 5

i=6: nums[6]=6
  6 > 3, remove index 5
  6 > 5, remove index 4
  deque: [6]
  Max = nums[6] = 6

i=7: nums[7]=7
  7 > 6, remove index 6
  deque: [7]
  Max = nums[7] = 7

Result: [3, 3, 5, 5, 6, 7]

Java Implementation


import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k == 0) return new int[0];

        Deque<Integer> deque = new ArrayDeque<>();
        int[] result = new int[nums.length - k + 1];
        int ri = 0;

        for (int i = 0; i < nums.length; i++) {
            // Remove indices outside window
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }

            // Remove smaller elements
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offer(i);

            // Add to result when window is complete
            if (i >= k - 1) {
                result[ri++] = nums[deque.peek()];
            }
        }

        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)
- Each element added to deque once: O(n)
- Each element removed from deque at most once: O(n)
- Total: O(n)
Space Complexity: O(k) - deque stores at most k indices

Key Takeaways

Monotonic deque maintains decreasing/increasing order
Store indices, not values (need to check window bounds)
Each element added/removed exactly once → O(n)
Perfect for "maximum/minimum in sliding window" problems