Sliding Window Maximum In Swift Using A Deque

October 17, 2023 |

Let’s keep going with algorithm problems. This one is called “sliding window maximum”, and it is a nice follow up to longest substring without repeating characters because the optimal solution also uses a sliding window. The twist is that we need a better data structure to keep the window efficient.

The problem looks like this:

Given an array of integers, nums
Given a window size, k
Return the maximum value in every contiguous window of size k

Here is the classic example:

let nums = [1, 3, -1, -3, 5, 3, 6, 7]
let k = 3

// result: [3, 3, 5, 5, 6, 7]

The windows are:

[1, 3, -1]      max is 3
[3, -1, -3]     max is 3
[-1, -3, 5]     max is 5
[-3, 5, 3]      max is 5
[5, 3, 6]       max is 6
[3, 6, 7]       max is 7

The slow solution

The simplest solution is to inspect every window and call max():

func maxSlidingWindowSlow(_ nums: [Int], _ k: Int) -> [Int] {
    guard k > 0, !nums.isEmpty, k <= nums.count else {
        return []
    }

    var result = [Int]()

    for start in 0...(nums.count - k) {
        let end = start + k
        let windowMax = nums[start..<end].max()!
        result.append(windowMax)
    }

    return result
}

This works, and for tiny inputs it is completely fine. The problem is that each window costs up to k checks, and there are n - k + 1 windows. That gives us a runtime of O((n - k + 1) * k), which is usually simplified to O(n * k).

We can do better.

The idea

We need a way to know the max value in the current window without rescanning the whole window every time it moves.

The trick is to store indices in a deque. A deque is a double-ended queue, which means we can efficiently add or remove values from both the front and the back.

After processing each index, our deque will follow two rules:

The front of the deque is the index of the largest value in the processed part of the current window.
The values represented by the deque are in strictly decreasing order from front to back.

That second rule is the magic. If a new value is larger than or equal to the values at the back of the deque, those older values can never become the maximum for this window or any future window that includes the new value. So we remove them.

Adding Swift Collections

Swift’s standard library does not include a deque, but Apple’s Swift Collections package does. In a Swift package, add it like this:

// swift-tools-version: 6.2
import PackageDescription

let package = Package(
    name: "Algorithms",
    dependencies: [
        .package(
            url: "https://github.com/apple/swift-collections.git",
            from: "1.5.1"
        )
    ],
    targets: [
        .target(
            name: "Algorithms",
            dependencies: [
                .product(name: "Collections", package: "swift-collections")
            ]
        )
    ]
)

Then import it:

import Collections

The O(n) solution

Here is the monotonic deque solution:

import Collections

func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
    guard k > 0, !nums.isEmpty, k <= nums.count else {
        return []
    }

    var result = [Int]()
    result.reserveCapacity(nums.count - k + 1)
    var deque = Deque<Int>() // Stores indices, not values.

    for index in nums.indices {
        // 1. Remove indices that are no longer inside the window.
        while let first = deque.first, first <= index - k {
            deque.popFirst()
        }

        // 2. Remove smaller or equal values from the back.
        while let last = deque.last, nums[last] <= nums[index] {
            deque.popLast()
        }

        // 3. Add the current index.
        deque.append(index)

        // 4. The first full window ends at k - 1.
        if index >= k - 1, let first = deque.first {
            result.append(nums[first])
        }
    }

    return result
}

There are a couple important details here.

First, the deque stores indices instead of values. That makes it easy to tell when an item has fallen out of the current window:

first <= index - k

Second, this line is what keeps the deque strictly decreasing:

while let last = deque.last, nums[last] <= nums[index] {
    deque.popLast()
}

If the current number is at least as large as the number at the back of the deque, the older number is no longer useful. The current number is newer, at least as large, and will stay in future windows longer.

Walking through one step

Using the example array, imagine we have reached the value 5 at index 4:

nums = [1, 3, -1, -3, 5, 3, 6, 7]
index = 4
k = 3
current window = [-1, -3, 5]

Before adding 5, the deque still contains index 1 for the value 3, but that index is expired because it no longer belongs to the current window. After removing that expired index, the deque contains indices for -1 and -3. Once 5 arrives, both of those values are smaller, so both get popped from the back. Then index 4 is appended. The front of the deque now points at 5, which is exactly the maximum for the current window.

That is the whole pattern. Remove expired indices from the front. Remove worse candidates from the back. Append the new index. Read the max from the front.

Complexity

The runtime is O(n). Even though there are nested while loops, each index is appended once and removed at most once. The total amount of deque work across the whole function is linear.

The auxiliary space complexity is O(k) because the deque only stores indices that could still belong to the current window. If we include the returned result array, the total space is O(n).

If you are solving this on an interview site that does not allow package imports, you can still use the same idea with an array and a head pointer. Just avoid calling removeFirst() on Array inside the loop, because that shifts elements and can quietly turn the solution back into something slower.