Start learning free

LESSON 395 OF 569 · SLIDING WINDOW

Sliding Window Maximum in Java: 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 9
    Ctrl + Enter to check

    JAVA · SLIDING WINDOW

    Sliding Window Maximum in Java, explained

    Problem overview

    The method maxSlidingWindow receives an int[] nums and a window size k. A window of k neighbouring values starts at the left end and slides right one position at a time until it reaches the right end. The method returns an int[] with the largest value of every window, from left to right. There are nums.length - k + 1 windows, so that is the length of the result.

    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]. Their maxima are [3, 3, 5, 5, 6, 7]. For [7, 2, 4] and k = 2 the answer is [7, 4]: once 7 has left the window, 4 is the largest value.

    Approach: keep only the values that can still win

    Scanning each window for its maximum takes O(n · k) time in total. With 100,000 values and a large k that is too slow. The lesson asks for O(n) time and O(n) extra space.

    The key observation: when a new value nums[i] enters the window, every earlier value in the window that is not bigger than it can never be a maximum again. It leaves the window before nums[i] does, and while it is inside, nums[i] is there too and at least as big. So we can throw such values away immediately.

    What remains are the candidates: the values that can still become a maximum. They are kept in a Deque (a queue that can be read and changed at both ends) as indexes, in increasing index order, and their values are strictly decreasing from front to back. That has three consequences:

    • The front holds the maximum of the current window.
    • The oldest candidate is at the front, so when an index slides out of the window, it is the front that leaves.
    • Storing indexes instead of values lets you tell whether the front is still inside the window.

    Here is the deque on the first example, as indexes and as the values they point to:

    i=0 value=1 indexes=[0] values=[1]
i=1 value=3 indexes=[1] values=[3]
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

    At i = 1 the value 3 removes the 1 before it. At i = 4 the value 5 removes everything. At i = 5 the 3 stays behind the 5, because it may be the maximum once the 5 has left.

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

    Step by step

    1. Create the deque candidates, a Deque<Integer> built as a new ArrayDeque<>(). Both ends work in O(1): peekFirst and pollFirst read and remove the front, peekLast and pollLast the back, and addLast adds at the back.
    2. Create the result array with nums.length - k + 1 slots, one per window.
    3. Loop over every index i. Each turn, i is the window's right end: the window is the k values that end at i.
    4. Drop the front if it left the window. The window now starts at i - k + 1, so an index of i - k or less is outside. Only one index can leave per turn, so one check is enough.
    5. Drop the back while it can never win again: while the deque isn't empty and nums[candidates.peekLast()] is <= nums[i].
    6. Remove the back with pollLast() inside that loop.
    7. Add i at the back. Now nums[i] is smaller than everything left in the deque, so the values still decrease from front to back.
    8. Record the maximum once the window is full, that is, when i >= k - 1: nums[candidates.peekFirst()] goes into result[i - k + 1], the window's own place in the result.
    9. Return result.

    The solution in Java

    class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> candidates = new ArrayDeque<>();
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            if (!candidates.isEmpty() && candidates.peekFirst() <= i - k) candidates.pollFirst();
            while (!candidates.isEmpty() && nums[candidates.peekLast()] <= nums[i]) {
                candidates.pollLast();
            }
            candidates.addLast(i);
            if (i >= k - 1) result[i - k + 1] = nums[candidates.peekFirst()];
        }
        return result;
    }
}

    Java details:

    • Deque is an interface, ArrayDeque a class. Declaring the variable as Deque<Integer> keeps the code to the methods you need. ArrayDeque is a resizable array used as a deque, and it is the usual choice for this kind of work.
    • Autoboxing. The deque holds Integer objects, but addLast(i) accepts an int and nums[candidates.peekLast()] unboxes the index to use it as an array subscript. Comparing with <= unboxes too. Compare two Integer objects with equals, never with ==.
    • peek and poll return null on an empty deque, where getFirst and removeFirst would throw. The isEmpty() checks come first, because unboxing a null into an int would throw a NullPointerException.
    • The order of the conditions. && stops at the first false, so peekFirst() and peekLast() are only read when the deque isn't empty.

    Complexity

    Time: O(n). The loop has n turns. The inner while can remove several indexes in one turn, but every index is added once and removed at most once, so across the whole run it removes at most n in total.

    Space: O(n) for the result and O(k) for the deque. The deque can hold at most k indexes at a time, because older ones are dropped from the front. The result has n - k + 1 entries.

    Edge cases and common mistakes

    • k = 1. Every window is a single value, so the result equals nums. [1] with k = 1 gives [1].
    • k = nums.length. There is one window. [9, 8, 7] with k = 3 gives [9].
    • Equal values. [4, 4, 4, 4] with k = 2 gives [4, 4, 4]. The <= in the while drops an equal older value, which is fine: the newer copy stays in the window longer. A strict < would also give correct maxima, but would keep more equal values in the deque.
    • A decreasing array. Nothing is ever removed from the back, and the front leaves one index at a time. For [5, 4, 3, 2, 1] with k = 3 the answer is [5, 4, 3].
    • Storing values instead of indexes. Then you can't tell when the front has left the window.
    • Off-by-one in the window start. The window that ends at i starts at i - k + 1, so an index of i - k is already out. The check must therefore include i - k itself, as <= does.
    • Result size. It is nums.length - k + 1, not nums.length.

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