239. Sliding Window Maximum

Array Queue Sliding Window Heap (Priority Queue)Monotonic Stack

Time: O(n)

Space: O(k)

Intuition

The maximum of every window of size k is needed. A naive approach rechecks each window in O(k) - O(nk) total. The insight: maintain a monotonically decreasing deque of indices. Any index with a smaller value than the incoming element can never be the maximum for any current or future window, so it is discarded immediately.

Algorithm

1Use a LinkedList<int> (deque) storing indices. Process each index i from 0 to n-1.
2Remove from the front any index <= i-k (outside the current window).
3Remove from the back any index whose value is <= nums[i] (they are dominated).
4Add i to the back of the deque.
5When i >= k-1 (first full window reached): the front of the deque is the index of the window maximum.

Example Walkthrough

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

1.i=0: deque=[0(1)]. i=1: 3>1, remove 0 -> deque=[1(3)]. i=2: -1<3, deque=[1(3),2(-1)]. Window [1,3,-1]: max=nums[1]=3.
2.i=3: -3<-1, deque=[1(3),2(-1),3(-3)]. Window [3,-1,-3]: max=nums[1]=3.
3.i=4: 5>everything, clear deque -> deque=[4(5)]. Window [-1,-3,5]: max=5.
4.i=5: 3<5, deque=[4(5),5(3)]. i=6: 6>3 and 6>5, clear -> deque=[6(6)]. max=6.
5.i=7: 7>6, clear -> deque=[7(7)]. max=7.

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

Common Pitfalls

•Remove from FRONT when out of window. Remove from BACK when dominated. These are two separate conditions, not one.
•Each element is pushed and popped at most once - total O(n), not O(nk).

239.cs

// Approach: Monotonic decreasing deque storing indices of candidates for the window maximum.
// For each new element at index i: remove from the back any indices whose values are <= nums[i].
// Those elements can never become the maximum for any future window, so they are useless.
// Remove from the front any index that is no longer inside the current window [i-k+1, i].
// The front of the deque always holds the index of the current window's maximum — O(1) query.
// Each index is pushed and popped at most once, so the total work across all windows is O(n).
// Time: O(n) Space: O(k) for the deque.

public class Solution
{
    public int[] MaxSlidingWindow(int[] nums, int k)
    {
        int n = nums.Length;
        int j = 0;
        int[] result = new int[n - k + 1];
        List<int> sw = new List<int>(k);

        for (int i = 0; i < n; i++)
        {
            while (sw.Count > 0 && sw[0] == i - k)
                sw.RemoveAt(0);

            while (sw.Count > 0 && nums[sw[sw.Count - 1]] < nums[i])
                sw.RemoveAt(sw.Count - 1);

            sw.Insert(sw.Count, i);

            if (i >= k - 1)
                result[j++] = nums[sw[0]];
        }

        return result;
    }
}

Was this solution helpful?