Sliding Window

December 20, 2023

Problem #

Given an array of integers and a sliding window of size k, find the maximum value in each window. The window slides one position to the right at a time.

Solution #

import collections

def max_sliding_window(nums, k):
    n = len(nums)
    if n == 0 or k == 0:
        return []

    deque = collections.deque()
    result = [-1] * (n - k + 1)
    for i in range(n):
        while deque and deque[0] < i - k + 1:
            deque.popleft()
        while deque and nums[deque[-1]] < nums[i]:
            deque.pop()
        deque.append(i)
        if i >= k - 1:
            result[i - k + 1] = nums[deque[0]]
    return result

# Test the function with an example
print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))

In this code, the max_sliding_window function takes a list of integers nums and an integer k as input, and returns a list of maximum values in each window. The algorithm works by maintaining a double-ended queue (deque) that contains the indices of the current elements within the sliding window. For each element in the input array, it first removes any elements from the deque whose corresponding index is outside the current window. Then, it removes any elements from the deque that have smaller values than the current element. Finally, it adds the current element’s index to the deque and updates the result list with the maximum value within the current window.

The complexity of this solution is O(n) as each element in the input array is processed exactly once. The space complexity is also O(n), as in the worst case, the deque can store all elements within the sliding window.

When run with the test case [1, 3, -1, -3, 5, 3, 6, 7] and a window size of 3, this function will return [3, 3, 5, 5, 6, 7], which represents the maximum value in each window as the sliding window moves through the array.