Start learning free

LESSON 400 OF 574 · SLIDING WINDOW

Sliding Window Maximum in Swift: 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

    SWIFT · SLIDING WINDOW

    Sliding Window Maximum in Swift, explained

    Problem overview

    The method maxSlidingWindow receives an array nums and an integer k. A window of k neighbouring values starts at the left end of nums and slides right one position at a time until it reaches the right end. The method returns the largest value of each window, from left to right. There are nums.count - k + 1 windows, so the result has that many values.

    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 answer is [3, 3, 5, 5, 6, 7]. For [7, 2, 4] with k = 2 the answer is [7, 4]: once the 7 has left the window, 4 is the largest value. For [1] with k = 1 the one window holds the only value.

    The statement asks for O(n) time. Finding each window's maximum from scratch costs O(n · k) in total, which is too slow when both numbers can reach 100,000.

    Approach: keep only the values that could still win

    Look at a window and at two values in it, where the earlier one is not bigger than the later one. The earlier value will leave the window first, and for as long as it stays, the later value is there too and is at least as big. So the earlier value can never be the window's maximum again, and there is no reason to remember it.

    That suggests a list of candidates: the values of the current window that could still become the maximum. If you always throw away the ones that a newcomer makes useless, the surviving values decrease from front to back. The front is then the largest one: the window's maximum. This structure is a monotonic deque, a queue you can take values from at both ends.

    Each turn does three things with the new index i:

    1. Drop the front if its index has left the window.
    2. Drop from the back every value that is not bigger than nums[i].
    3. Add i at the back.

    When the window is full, the front holds the answer. The deque stores indexes, not values: an index tells you both which value it stands for and whether it is still inside the window.

    Here is the first example. After each turn, the deque holds these indexes, with the values they stand for:

    i=0 value=1 deque indexes=[0] values=[1]
i=1 value=3 deque indexes=[1] values=[3]
i=2 value=-1 deque indexes=[1, 2] values=[3, -1] max=3
i=3 value=-3 deque indexes=[1, 2, 3] values=[3, -1, -3] max=3
i=4 value=5 deque indexes=[4] values=[5] max=5
i=5 value=3 deque indexes=[4, 5] values=[5, 3] max=5
i=6 value=6 deque indexes=[6] values=[6] max=6
i=7 value=7 deque indexes=[7] values=[7] max=7

    At i = 1 the 3 pushes the 1 out of the deque. At i = 4 the 5 clears everything. At i = 5 the 3 stays behind the 5, because it might be the maximum once the 5 has left. Every deque is in decreasing order of values, and the front is the maximum.

    Step by step

    1. Create candidates, an empty array of Int that plays the deque. It holds indexes of values that can still be the maximum, with their values decreasing from front to back.
    2. Add head, a var starting at 0: the position of the deque's front inside candidates. Swift has no built-in deque, and removing an array's first element moves all the others, which costs O(n). Moving head forward is O(1), and the entries before it are ignored.
    3. Create result for the maxima.
    4. Loop over i from 0 to nums.count - 1. On each turn, i is the window's right end.
    5. 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. Indexes are in increasing order and only one can leave per turn, so one check is enough. The check also asks head < candidates.count, to make sure the deque is not empty.
    6. Drop the back while it can't win. While the deque is not empty and nums[candidates.last!] is <= nums[i], remove the back with removeLast().
    7. Add i at the back with append. It is smaller than everything left in the deque, so the values still decrease.
    8. Record the maximum once the window is full. When i >= k - 1, append nums[candidates[head]] to result. Before that, the window holds fewer than k values.
    9. Return result.

    The solution in Swift

    class Solution {
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        var candidates = [Int]()
        var head = 0
        var result = [Int]()
        for i in 0..<nums.count {
            if head < candidates.count && candidates[head] <= i - k { head += 1 }
            while head < candidates.count && nums[candidates.last!] <= nums[i] {
                candidates.removeLast()
            }
            candidates.append(i)
            if i >= k - 1 { result.append(nums[candidates[head]]) }
        }
        return result
    }
}

    The Swift details worth knowing:

    • An array as a deque. append and removeLast() work at the end of an array in constant time. The front is simulated by head. The cost is that the array keeps the stale entries before head, so it can grow to n entries.
    • candidates.last!. last is an optional, because an array can be empty. The ! unwraps it and crashes on nil. It is safe here because head < candidates.count is checked first, and && stops at the first false part, so last is only read when something is in the deque.
    • Why head < candidates.count and not !candidates.isEmpty. Entries before head are stale. The deque is empty when head has reached the end of the array, even though the array is not.
    • <=, not <, in the back test. With equal values the older one can go: the newer one outlasts it. For [4, 4, 4, 4] with k = 2, the deque never holds more than one index, and the result is [4, 4, 4].
    • The result array grows by one value per window, so there is no need to size it in advance.

    Complexity

    Time: O(n). The loop runs n times. Inside it, the front check moves head by at most 1, and the while loop removes entries from the back. Each index is appended once and removed at most once, so all the removals together take at most n steps, whatever k is.

    Space: O(n). candidates can reach n entries, for example with strictly decreasing numbers when nothing is ever removed from the back, and result holds n - k + 1 values.

    Edge cases and common mistakes

    • k = 1. Every window is a single value, so the result equals the input: [9, 8, 7] with k = 1 gives [9, 8, 7].
    • k equal to the length. There is one window. [1, 2, 3, 4, 5] with k = 5 gives [5].
    • Decreasing input. [5, 4, 3, 2, 1] with k = 2 gives [5, 4, 3, 2]. Nothing is ever removed from the back, and the front check does all the work.
    • Equal values. Dropping on <= keeps the deque strictly decreasing, so the front is always the right answer.
    • Storing values instead of indexes. Without the index, you can't tell when the front has left the window.
    • Reading the maximum too early. Before i reaches k - 1 the window is not full yet, so nothing is recorded.
    • Removing the front with removeFirst(). It works, but it moves every other element, which costs O(n) and can bring the whole method back to quadratic time.

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