Sliding Window Maximum

Description

239. 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 an array containing the maximum element in each sliding window.

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

Explanation:

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
 

Example 2:
Input: nums = [1], k = 1
Output: [1]

Constraints:

• $1\le \text{nums.length}\le 10^5$
• $-10^4\le \text{nums}[i]\le 10^4$
• $1\le k\le \text{nums.length}$

---

Approach 1: Max-Heap / Priority Queue ($O(N\log N)$)

Intuition

Use a Max-Heap that stores pairs of [value, index]. For each element, push it into the heap. Before reading the top of the heap, lazily remove any element at the top whose index falls outside the current window boundary (index <= i - k).

import java.util.PriorityQueue;
 
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        // Max Heap storing {value, index}
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
 
        for (int i = 0; i < n; i++) {
            maxHeap.offer(new int[]{nums[i], i});
 
            // Remove elements at the top that are out of bounds for the current window
            while (maxHeap.peek()[1] <= i - k) {
                maxHeap.poll();
            }
 
            // Once the first window of size k is formed, record the max
            if (i >= k - 1) {
                result[i - k + 1] = maxHeap.peek()[0];
            }
        }
 
        return result;
    }
}
 

Complexity

• Time Complexity: $O(N\log N)$ — Pushing up to $N$ elements into a heap of size up to $N$ takes $O(\log N)$ time per element.
• Space Complexity: $O(N)$ — Stores up to $N$ element-index pairs in the priority queue (results in TLE/MLE on extreme inputs).

---

Most Optimized Solution: Monotonic Deque ($O(N)$)

Intuition

Maintain a Double-Ended Queue (Deque) storing array indices in monotonically decreasing order of their corresponding values in nums:

1. Evict Out-of-Bound Indices: Remove the front index if deque.peekFirst() <= i - k.
2. Maintain Decreasing Order: Before adding nums[i], pop all indices from the back of the deque (deque.peekLast()) whose values are smaller than or equal to nums[i]. Those smaller elements can never be the window maximum because nums[i] is both larger and arrived later.
3. Record Window Max: The front of the deque (deque.peekFirst()) always points to the index of the largest element in the current window.

import java.util.ArrayDeque;
import java.util.Deque;
 
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>(); // Stores indices
 
        for (int i = 0; i < n; i++) {
            // 1. Evict elements outside the current window boundary
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
 
            // 2. Remove smaller elements from the back (they can't be window max)
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
 
            // 3. Append current index to back
            deque.offerLast(i);
 
            // 4. Front of deque contains maximum element for current window
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
 
        return result;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Each index is pushed and popped from the deque at most once across the entire array.
• Space Complexity: $O(k)$ — The deque holds at most $k$ indices at any time.

---

Easy Memory Rule

“Keep a decreasing Deque of indices. Pop stale indices from the front, pop smaller elements from the back, and the max is always at peekFirst().”

Deque Cheat Sheet: Front vs. Back

• Front (peekFirst): Holds the index of the maximum element for the current window.
  • Action (pollFirst): Pop from front when an index expires ($\text{index}\le i-k$).
• Back (peekLast): Handles incoming elements.
  • Action (pollLast): Pop from back as long as $\text{nums}[\text{back}]<\text{nums}[i]$ (purges smaller values that can never be max again).
  • Action (offerLast): Always append the current index $i$ to the back.

---

What Each of the 4 Code Steps Means

1. Evict Expired Index (pollFirst): Checks if the front index has fallen outside the left edge of the sliding window ($\text{index}\le i-k$). If so, it removes it from the front.
   • Window size is i-k+1 to i and first is left side so if less then we need to move left

if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) 
		deque.pollFirst();

2. Purge Smaller Values (pollLast): Pops indices from the back whose values are smaller than nums[i]. These smaller values can never be the maximum again because nums[i] is both larger and will stay in the window longer.

while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
		deque.pollLast();

3. Append Current Index (offerLast): Adds the current index i to the back of the deque to maintain the strictly decreasing order.

deque.offerLast(i)

4. Record Window Max (peekFirst): Once a full window of size $k$ is formed ($i\ge k-1$), the index at the front (peekFirst()) holds the maximum value for that window.

if (i >= k - 1)
    result[i - k + 1] = nums[deque.peekFirst()];

---

Step-by-Step Trace: nums = [1, 3, -1, -3, 5], k = 3

$i=0$ (nums[0] = 1)

1. Evict Expired: !isEmpty() $\to$ false (Skip)
2. Purge Smaller: !isEmpty() $\to$ false (Skip)
3. Append: offerLast(0) $\to$ Deque: [0]
4. Record Max: 0 >= 2 $\to$ false (Skip)

---

$i=1$ (nums[1] = 3)

1. Evict Expired: 0 <= -2 $\to$ false (Skip)
2. Purge Smaller: nums[0] (1) < 3 $\to$ true $\to$ pollLast() (removes 0)
3. Append: offerLast(1) $\to$ Deque: [1]
4. Record Max: 1 >= 2 $\to$ false (Skip)

---

$i=2$ (nums[2] = -1)

1. Evict Expired: 1 <= -1 $\to$ false (Skip)
2. Purge Smaller: nums[1] (3) < -1 $\to$ false (Stop)
3. Append: offerLast(2) $\to$ Deque: [1, 2]
4. Record Max: 2 >= 2 $\to$ true $\to$ result[0] = nums[1] = 3

---

$i=3$ (nums[3] = -3)

1. Evict Expired: 1 <= 0 $\to$ false (Skip)
2. Purge Smaller: nums[2] (-1) < -3 $\to$ false (Stop)
3. Append: offerLast(3) $\to$ Deque: [1, 2, 3]
4. Record Max: 3 >= 2 $\to$ true $\to$ result[1] = nums[1] = 3

---

$i=4$ (nums[4] = 5)

1. Evict Expired: 1 <= 1 $\to$ true $\to$ pollFirst() (removes 1)
2. Purge Smaller:
   • nums[3] (-3) < 5 $\to$ true $\to$ pollLast() (removes 3)
   • nums[2] (-1) < 5 $\to$ true $\to$ pollLast() (removes 2)
3. Append: offerLast(4) $\to$ Deque: [4]
4. Record Max: 4 >= 2 $\to$ true $\to$ result[2] = nums[4] = 5

Final Result

result = [3, 3, 5]

---

What is a Deque?

A Deque (short for Double-Ended Queue) is a linear data structure that allows elements to be added or removed from both ends (front and back) in $O(1)$ constant time.

It combines the properties of both a Queue (FIFO) and a Stack (LIFO):

• Front operations: addFirst(), pollFirst(), peekFirst()
• Back operations: addLast(), pollLast(), peekLast()

In Java, it is implemented using the ArrayDeque class.

---

What Type of Deque We Use in “Sliding Window Maximum”

We use a Monotonic Decreasing Deque that stores array indices (rather than raw values).

• Monotonic Decreasing Order: The numbers corresponding to the stored indices are maintained in strictly decreasing order from front to back:

$\text{nums}[\text{deque.peekFirst()}]>\text{nums}[\dots ]>\text{nums}[\text{deque.peekLast()}]$

• Front of the Deque: Always holds the index of the maximum element in the current sliding window.

---

Why We Use It Here

1. Instant $O(1)$ Window Maximum

Because the deque maintains decreasing order, the largest element for the current window is always positioned at the very front (deque.peekFirst()). No scanning or searching is required.

2. Elimination of Useless Elements

When processing a new element nums[i]:

• Any element currently in the deque that is **smaller than or equal to nums[i]** can never be the maximum of the current or future windows because nums[i] is both larger and will stay in the sliding window longer.
• We efficiently purge these smaller elements from the back of the deque using pollLast().

3. $O(1)$ Out-of-Bounds Eviction

As the window slides forward, the oldest element leaves the window. We check if the index at the front of the deque is out of bounds (deque.peekFirst() <= i - k). If it is, we discard it from the front using pollFirst().

4. Overall $O(N)$ Time Complexity

By using a Deque, every index is added once and removed at most once across the entire array run. This reduces the time complexity from an $O(N\times k)$ brute-force search down to $O(N)$.