Sliding Maximum - Implementation

Here's the approach in pseudo-code:

function maxSlidingWindow(nums, k)
    deque := empty deque of indices
    result := []
    for i from 0 to n-1
        // Remove indices outside window
        while deque not empty and deque.front() < i - k + 1
            deque.popFront()
        // Remove smaller elements from back
        while deque not empty and nums[deque.back()] <= nums[i]
            deque.popBack()
        deque.pushBack(i)
        if i >= k - 1 then
            result.append(nums[deque.front()])
    return result

Time: $O(n)$ because each index is pushed and popped at most once. Space: $O(k)$ for the deque.

Time complexity: $O(n)$.

Space complexity: $O(k)$.