Sliding Window Maximum

LeetCode 239 | Difficulty: Hard

Hard

Problem Description

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.

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 <= nums.length <= 10^5`

- `-10^4 <= nums[i] <= 10^4`

- `1 <= k <= nums.length`

Topics: Array, Queue, Sliding Window, Heap (Priority Queue), Monotonic Queue

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

---

Solutions

Solution 1: C# (Best: 272 ms)

Metric	Value
Runtime	272 ms
Memory	34.5 MB
Date	2019-02-25

Solution

public class Solution {
    public int[] MaxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.Length==0 || k == 0) return nums;

    int len = nums.Length;
    int[] ans = new int[len - k + 1];
    int ri = 0;

    LinkedList<int> q = new LinkedList<int>();

    // Queue stores indices of array, and 
    // values are in decreasing order.
    // So, the first node in queue is the max in window
    for (int i = 0; i < len; i++)
    {
        // 1. remove element from head until first number within window
        if (q.Count > 0 && q.First.Value < i-k+1)
        {
            q.RemoveFirst();
        }

        // 2. before inserting i into queue, remove from the tail of the
        // queue indices with smaller value they array[i]
        while (q.Count > 0 && nums[q.Last.Value] <= nums[i])
        {
            q.RemoveLast();
        }

        q.AddLast(i);

        if(i >= k-1)
        {
            ans[ri++] = nums[q.First.Value];
        }
    }

    return ans;
}
}

📜 1 more C# submission(s)

Submission (2019-02-25) — 272 ms, 34.6 MB

public class Solution {
    public int[] MaxSlidingWindow(int[] nums, int k) {
        if (k == 0) return nums;

    int len = nums.Length;
    int maxArrayLen = len - k + 1;
    int[] ans = new int[maxArrayLen];

    LinkedList<int> q = new LinkedList<int>();

    // Queue stores indices of array, and 
    // values are in decreasing order.
    // So, the first node in queue is the max in window
    for (int i = 0; i < len; i++)
    {
        // 1. remove element from head until first number within window
        if (q.Count > 0 && q.First.Value + k <= i)
        {
            q.RemoveFirst();
        }

        // 2. before inserting i into queue, remove from the tail of the
        // queue indices with smaller value they array[i]
        while (q.Count > 0 && nums[q.Last.Value] <= nums[i])
        {
            q.RemoveLast();
        }

        q.AddLast(i);

        // 3. set the max value in the window (always the top number in
        // queue)
        int index = i + 1 - k;
    
        if (index >= 0)
        {
            ans[index] = nums[q.First.Value];
        }
    }
        return ans;
}
}

---

Complexity Analysis

Approach	Time	Space
Sliding Window	$O(n)$	$O(k)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: How about using a data structure such as deque (double-ended queue)?

Hint 2: The queue size need not be the same as the window’s size.

Hint 3: Remove redundant elements and the queue should store only elements that need to be considered.