Start learning free

LESSON 395 OF 569 · SLIDING WINDOW

Sliding Window Maximum in Python: O(n) with a Monotonic Deque

Practice O(n) Read the full explanation

You are given a list of integers nums and an integer k. A window of size k starts at the left end of nums and slides to the right one position at a time, until it reaches the right end. At each position, the window covers k neighbouring values.

Return a list with the largest value of each window, from left to right.

 

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]
Explanation: There is one window, and it holds the only value.

Example 3:

Input: nums = [7, 2, 4], k = 2
Output: [7, 4]
Explanation: The windows are [7, 2] and [2, 4]. Once 7 has left the window, 4 is the largest value.

 

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

Note:

Your algorithm should run in O(n) time, where n is the length of nums, and use O(n) extra space. Finding each window's maximum from scratch takes O(n · k) time, too slow for the largest tests.

STEP 1 OF 9
    Ctrl + Enter to check

    PYTHON · SLIDING WINDOW

    Sliding Window Maximum in Python, explained

    Problem overview

    The method maxSlidingWindow receives a list nums and an integer k. A window of k neighbouring values starts at the left end and moves right one position at a time. The method returns the largest value of every window, from left to right, so a list of n - k + 1 numbers.

    For nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3 the windows are [1, 3, -1], [3, -1, -3], [-1, -3, 5], [-3, 5, 3], [5, 3, 6] and [3, 6, 7], and the result is [3, 3, 5, 5, 6, 7]. With nums = [7, 2, 4] and k = 2 the result is [7, 4]: once the 7 has left the window, the 4 is the largest value.

    The lesson asks for O(n) time and O(n) extra space. Calling max on every window costs O(n · k), which is too slow when both are large.

    Approach: keep only the values that can still win

    When a new value nums[i] enters the window, any earlier value in the window that is not bigger can never be the maximum again. It sits to the left, so it leaves the window first, and for as long as it stays, nums[i] is there too and is at least as big. Such values can be thrown away at once.

    That leaves a list of candidates: values that are still in the window and are strictly bigger than everything that came after them. Read from the oldest to the newest, they decrease. The first candidate is therefore always the maximum of the window.

    The candidates live in a deque (a double-ended queue), which adds and removes at both ends in constant time. The deque stores indexes, not values, so the code can tell when the oldest candidate has slid out of the window, and it reads the values through nums. Each turn does three things:

    • drop the front index if it has left the window;
    • drop indexes from the back while their values are not bigger than nums[i];
    • add i at the back, and once the window is full, report nums[candidates[0]].

    Each index enters the deque once and leaves it at most once, so all the work adds up to O(n), however large k is.

    Here is the first example, nums = [1, 3, -1, -3, 5, 3, 6, 7] with k = 3. The table shows the deque's indexes and values after each turn:

    inums[i]indexes in the dequetheir valuesreported
    01[0][1](window not full)
    13[1][3](window not full)
    2-1[1, 2][3, -1]3
    3-3[1, 2, 3][3, -1, -3]3
    45[4][5]5
    53[4, 5][5, 3]5
    66[6][6]6
    77[7][7]7

    At i = 4 the value 5 beats everything in the deque, so all three entries are removed. The reported values are [3, 3, 5, 5, 6, 7].

    Step by step

    1. Create the empty deque candidates with deque(). It holds indexes whose values decrease from front to back.
    2. Create the empty list result for the maxima.
    3. Loop over every index i. Each turn, i is the right end of the window: the k values that end at i.
    4. Drop the front if it expired. The window now starts at i - k + 1, so an index of i - k or less is outside it. Indexes arrive in increasing order, so the oldest is at the front, and one check per turn is enough because at most one index expires per turn.
    5. Write the while loop that runs while the deque is not empty and the value at its back, nums[candidates[-1]], is <= nums[i].
    6. Inside it, call candidates.pop(), which removes from the back.
    7. Append i with candidates.append(i). Every value left in the deque is bigger than nums[i], so the order stays decreasing.
    8. If the window is full, i >= k - 1, append nums[candidates[0]] to result. Before that the window holds fewer than k values.
    9. Return result.

    The solution in Python

    class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        candidates = deque()
        result = []
        for i in range(len(nums)):
            if candidates and candidates[0] <= i - k:
                candidates.popleft()
            while candidates and nums[candidates[-1]] <= nums[i]:
                candidates.pop()
            candidates.append(i)
            if i >= k - 1:
                result.append(nums[candidates[0]])
        return result

    Python details worth knowing:

    • The deque. deque comes from the collections module; in a file of your own, add from collections import deque. Its append and pop work at the right end, popleft at the left end, and candidates[0] and candidates[-1] read the two ends. A plain list would do the right end well, but list.pop(0) shifts every remaining item, which is why a deque is the right tool.
    • Truthiness. candidates and ... uses the fact that an empty deque counts as false, so the right-hand side is only evaluated when the deque has something in it. That prevents an IndexError on candidates[0] or candidates[-1].
    • Indexes, not values. The expression nums[candidates[-1]] first reads the index at the back, then looks up its value.
    • Negative indexes. candidates[-1] is the last element, the back of the deque.

    Complexity

    Time: O(n). The outer loop runs n times. The inner while loop looks like a loop within a loop, but every pass of it removes an index that was added earlier, and each index is added exactly once. So all the removals together cost at most n steps, and the whole function stays linear regardless of k.

    Space: O(n). The deque holds at most k indexes (for a list in decreasing order, it fills up to the window size), and the result holds n - k + 1 numbers. Both are bounded by n.

    Edge cases and common mistakes

    • Forgetting to expire the front. Without the popleft check, [7, 2, 4] with k = 2 returns [7, 7]: the 7 stays in front long after it has left the window.
    • Window of one. With k = 1 every window is a single value, so the result equals nums. For [1, -1] the method returns [1, -1].
    • Window as big as the list. With k = len(nums) there is one window. For [9, 8, 7] and k = 3 the result is [9].
    • Decreasing and increasing lists. For [4, 3, 2, 1] with k = 2 the deque grows to the window size and the result is [4, 3, 2]. For [1, 2, 3, 4] each new value clears the deque and the result is [2, 3, 4].
    • Equal values. With <= in the while test, an equal value at the back is replaced by the newer one, which stays in the window longer. For [5, 5, 5] and k = 2 the result is [5, 5].
    • Negative numbers. Nothing special is needed. For [-5, -3, -4] and k = 2 the result is [-3, -3].
    • Reporting too early. Without the i >= k - 1 test, the method would append a maximum for the first k - 1 partial windows, and the result would be too long.

    Testing

    • nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 gives [3, 3, 5, 5, 6, 7].
    • nums = [1], k = 1 gives [1].
    • nums = [7, 2, 4], k = 2 gives [7, 4].
    • nums = [4, 3, 2, 1], k = 2 gives [4, 3, 2].
    • nums = [1, 2, 3, 4], k = 2 gives [2, 3, 4].
    • nums = [5, 5, 5], k = 2 gives [5, 5].
    • nums = [-5, -3, -4], k = 2 gives [-3, -3].
    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free