Start learning free

LESSON 395 OF 569 · SLIDING WINDOW

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

Practice O(n) Read the full explanation

You are given an array 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 an array 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 10
    Ctrl + Enter to check

    JAVASCRIPT · SLIDING WINDOW

    Sliding Window Maximum in JavaScript, explained

    Problem overview

    The method maxSlidingWindow(nums, k) receives an array of integers and a window size k. The window starts over the first k values and moves one place to the right at a time until it reaches the end of the array. The function returns the largest value of each window position, from left to right, so the result has nums.length - k + 1 entries.

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

    The statement sets a budget of O(n) time and O(n) extra space.

    Approach: keep only the values that can still win

    The direct solution scans each window for its maximum. That is O(n · k) work, and with n up to 100,000 and a large k it is too slow.

    The key observation is that many values in a window can never be its maximum. Suppose a value a sits to the left of a value b in the window and a <= b. The value a leaves the window first, so for as long as a is in the window, b is there too and is at least as big. So a can be forgotten.

    If you forget every such value, the ones that remain are in decreasing order from left to right, and the first of them is the maximum. That structure is a deque (a double-ended queue) of indexes, with values decreasing from the front to the back. Three operations keep it up to date as each new index i arrives:

    • Drop the front if its index has slid out of the window.
    • Drop from the back every index whose value is <= nums[i], because nums[i] beats it.
    • Add i at the back.

    Each index is added once and removed at most once, so all the work adds up to O(n), whatever k is.

    Here is the deque after each step for nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, shown as indexes and as the values they point to:

    i=0 value 1:  indexes [0]        values [1]          (window not full)
i=1 value 3:  indexes [1]        values [3]          (window not full)
i=2 value -1: indexes [1,2]      values [3,-1]       max 3
i=3 value -3: indexes [1,2,3]    values [3,-1,-3]    max 3
i=4 value 5:  indexes [4]        values [5]          max 5
i=5 value 3:  indexes [4,5]      values [5,3]        max 5
i=6 value 6:  indexes [6]        values [6]          max 6
i=7 value 7:  indexes [7]        values [7]          max 7

    When 5 arrives at index 4, it removes 3, -1 and -3 from the back. The index 1 would also have left the window at that point, since the window is now indexes 2 to 4.

    Step by step

    1. Create candidates, an empty array that works as the deque. It holds indexes, not values: an index shows both which value it is and when it leaves the window.
    2. Create head, starting at 0. JavaScript arrays have no deque operations, so head marks the front. Entries before head are ignored. Removing the first element with shift would move every other element, while advancing head is constant time.
    3. Create result, the array of maxima.
    4. Loop over every index i. Each turn, i is the right end of the window.
    5. Drop the front when it has left the window. The window starts at i - k + 1, so an index of i - k or less is outside. Indexes arrive in increasing order, so the oldest is at the front, and only one index can leave per turn.
    6. Loop while the back is beaten. While the deque is not empty and the value at its back is <= nums[i], that value can never be a maximum again. Checking head < candidates.length first stops the loop from popping entries that already left at the front.
    7. Remove the back with pop().
    8. Add i at the back with push(i). Its value is now smaller than everything left in the deque, so the values stay decreasing.
    9. Record the maximum once the window is full. When i >= k - 1, the window has k values and its maximum is at the front, nums[candidates[head]].
    10. Return result.

    The solution in JavaScript

    class Solution {
    maxSlidingWindow(nums, k) {
        let candidates = [];
        let head = 0;
        let result = [];
        for (let i = 0; i < nums.length; i++) {
            if (head < candidates.length && candidates[head] <= i - k) head++;
            while (head < candidates.length && nums[candidates[candidates.length - 1]] <= nums[i]) {
                candidates.pop();
            }
            candidates.push(i);
            if (i >= k - 1) result.push(nums[candidates[head]]);
        }
        return result;
    }
}

    JavaScript details worth knowing:

    • An array as a deque. push and pop work on the end of an array in constant time. shift, which removes the first element, has to renumber the rest, so using it as the dequeue operation can make the loop quadratic on large inputs. The head index avoids that, at the cost of keeping the dropped entries in memory until the function returns, which is why the space is O(n).
    • Short-circuit &&. In both conditions, head < candidates.length is evaluated first. If it is false, the right side is not evaluated, so the code never reads candidates[head] or the back of an empty deque.
    • Indexes into indexes. The expression nums[candidates[head]] is two lookups: first the index stored at the front, then the value at that index.

    Complexity

    Time: O(n). The for loop runs n times. The while loop can run several times in one turn, but each pop removes an index that was pushed earlier, and every index is pushed exactly once. So the pops add up to at most n over the whole run, and the front moves forward at most n times.

    Space: O(n). result holds n - k + 1 values, and candidates can hold up to n indexes, for example when nums is sorted in decreasing order.

    Edge cases and common mistakes

    • k = 1. Every window is a single value, so the result equals the input. [2, 1, 3] with k = 1 gives [2, 1, 3].
    • k equal to the length. There is one window. [9, 8, 7] with k = 3 gives [9].
    • Equal values. [5, 5, 5, 5] with k = 3 gives [5, 5]. The back is removed when it is <= the new value, not only when it is strictly smaller. Dropping the older of two equal values is safe because the newer one stays in the window longer.
    • A decreasing array. [4, 3, 2, 1] with k = 2 gives [4, 3, 2]. Nothing is ever popped from the back, so the maximum leaves through the front and the front check matters.
    • An increasing array. [1, 2, 3, 4] with k = 2 gives [2, 3, 4]. Each new value clears the deque and the front is always the newest index.
    • Storing values instead of indexes. With values alone you cannot tell when the front has left the window, and duplicates become ambiguous.
    • Recording a maximum too early. Before index k - 1 the window is not full yet, so nothing is added to result.
    • Using shift to remove the front. It gives the right answers but can slow down large inputs, as described above.

    Testing

    • nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 gives [3, 3, 5, 5, 6, 7].
    • nums = [7, 2, 4], k = 2 gives [7, 4].
    • nums = [1], k = 1 gives [1].
    • 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, 5], k = 3 gives [5, 5].
    • An array of 100,000 values with k = 1000: the result has 99,001 entries and matches a brute-force scan of every window, which takes much longer to compute.
    Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free