Course4all
Join us on telegram
Home/dsa/Heap / Priority Queue/Sliding Window Maximum

Sliding Window Maximum

Master this topic with zero to advance depth.

Sliding Window Maximum

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.

Visual Representation

nums = [1,3,-1,-3,5,3,6,7], k = 3 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
Hard

Examples

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

Level I: Max-Heap (Lazy Removal)

Intuition

A Max-Heap easily gives us the maximum element. However, when the window slides, removing the element that left the window from the middle of the heap is O(N). Instead, we can use lazy removal: we store (value, index) in the heap. We only remove elements from the top of the heap if their index is outside the current window's bounds.

Thought Process

  1. Use a Max-Heap storing pairs of (nums[i], i).
  2. Initialize the heap with the first k elements.
  3. The max of the first window is the top of the heap.
  4. Slide the window from i = k to N - 1:
    • Push (nums[i], i) into the heap.
    • Check the top of the heap. If its index is <= i - k, it means it's outside the window. Pop it.
    • Keep popping until the top is inside the window.
    • Record the top's value as the max for the current window.
⏱ O(N log N) because we might insert N elements, and each insertion/extraction is logarithmic💾 O(N) in the worst case if elements are continuously increasing (they are never lazily removed until the end)

Detailed Dry Run

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

  1. Init k=3: Heap = [(3,1), (1,0), (-1,2)]. Max = 3.
  2. i=3 (val=-3): Push (-3,3). Heap = [(3,1), (1,0), (-1,2), (-3,3)]. Top idx=1 is inside window (3-3=0, 1>0). Max = 3.
  3. i=4 (val=5): Push (5,4). Heap = [(5,4), (3,1),...]. Top idx=4 is inside. Max = 5.
  4. i=5 (val=3): Push (3,5). Heap = [(5,4), ...]. Top idx=4 is inside. Max = 5.
java
import java.util.*;

public class Main {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int i = 0; i < k; i++) {
            maxHeap.offer(new int[]{nums[i], i});
        }
        
        int[] res = new int[nums.length - k + 1];
        res[0] = maxHeap.peek()[0];
        
        for (int i = k; i < nums.length; i++) {
            maxHeap.offer(new int[]{nums[i], i});
            while (maxHeap.peek()[1] <= i - k) {
                maxHeap.poll();
            }
            res[i - k + 1] = maxHeap.peek()[0];
        }
        return res;
    }

    public static void main(String[] args) {
        int[] res = maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3);
        System.out.println(Arrays.toString(res)); // [3, 3, 5, 5, 6, 7]
    }
}
Approach 2

Level II: Balanced BST / Sorted List

Intuition

Maintain a sorted collection of the elements currently in the sliding window. As the window slides, remove the element that is falling out and insert the new element. The maximum is always the last element in the sorted collection.

⏱ O(N log k) where k is the window size💾 O(k) to store the window elements

Detailed Dry Run

nums = [1,3,-1], k = 3

  1. Initial window [1, 3, -1]. Sorted: [-1, 1, 3]. Max = 3.
  2. Slide to [3, -1, -3]: Remove 1, Insert -3. Sorted: [-3, -1, 3]. Max = 3.
  3. Slide to [-1, -3, 5]: Remove 3, Insert 5. Sorted: [-3, -1, 5]. Max = 5.
java
import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        TreeMap<Integer, Integer> window = new TreeMap<>();
        int[] res = new int[nums.length - k + 1];
        
        for (int i = 0; i < nums.length; i++) {
            // Add current number
            window.put(nums[i], window.getOrDefault(nums[i], 0) + 1);
            
            // Remove old number if window is full
            if (i >= k) {
                int old = nums[i - k];
                if (window.get(old) == 1) window.remove(old);
                else window.put(old, window.get(old) - 1);
            }
            
            // Record max
            if (i >= k - 1) {
                res[i - k + 1] = window.lastKey();
            }
        }
        return res;
    }
}
Approach 3

Level III: Monotonic Deque (Optimal)

Intuition

If we have a descending sequence in the window, say [5, 4, 2], the maximum is 5. If we add a new number 6, then 5, 4, 2 are completely useless because they are smaller than 6 and will leave the window before 6 does! Thus, a monotonically decreasing deque can perfectly track the useful candidates for being the window's max.

Thought Process

  1. Maintain a deque (double-ended queue) of indices.
  2. The elements represented by indices in the deque are kept in strictly descending order.
  3. Loop over nums[i] from 0 to N-1:
    • Maintain Window Bound: If the index at the front of the deque is out of the current window (< i - k + 1), remove it from the front.
    • Maintain Descending Order: While the deque is not empty and the element at the back is < nums[i], remove it from the back. (They are useless now).
    • Add current index i to the back.
    • Once i >= k - 1, the window is fully formed. The maximum is always at the front of the deque, so append nums[deque.front()] to the result.
⏱ O(N) because each element is pushed to and popped from the deque at most once💾 O(k) to store elements in the deque at any given time

Detailed Dry Run

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

  1. i=0, v=1: dq=[0 (val:1)]
  2. i=1, v=3: 1 < 3, pop 0. dq=[1 (val:3)]
  3. i=2, v=-1: -1 < 3, keep. dq=[1, 2]. Window full, max=nums[1]=3
  4. i=3, v=-3: -3 < -1, keep. dq=[1, 2, 3]. max=nums[1]=3
  5. i=4, v=5: front 1 out of bounds (1 <= 4-3). pop 1. val 5 > -1, -3. pop 2, 3. push 4. dq=[4 (val:5)]. max=5
java
import java.util.*;

public class Main {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k <= 0) return new int[0];
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> q = new ArrayDeque<>();
        
        for (int i = 0; i < nums.length; i++) {
            // Remove indices that are out of bounds
            while (!q.isEmpty() && q.peekFirst() < i - k + 1) {
                q.pollFirst();
            }
            // Remove smaller elements in k range
            while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) {
                q.pollLast();
            }
            
            q.offerLast(i);
            // Add to result when window reaches size k
            if (i >= k - 1) {
                res[i - k + 1] = nums[q.peekFirst()];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] res = maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3);
        System.out.println(Arrays.toString(res)); // [3, 3, 5, 5, 6, 7]
    }
}
← Previous QuestionFind Median from Data Stream
Next Question →Trapping Rain Water II