Another Sliding Window - find each `k-size` window the maximum num. from an integer array/list

Question

I've searched this site and find many similar questions, but not exactly the same as the one I'll post.

This attempts to solve Leetcode 239:

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

The subject is - given an integer array, and positive integer k, denoting the sliding window size. Each time you can only slide from left to right one position, try to find each windows maximum number and output these maximum number into an output list. [Note - the given list could be very large ~ 1 Million (nums)]

For example: Given a nums array = [99, 74, 48, 27, 56, 88, 66, 77, 101]; k = 3 Output should be: [99, 74, 56, 88, 88, 88, 101]

I've tried to solve this in Python, and wonder if it could be further optimized and improved.

def maxSliding(nums: List[int], k: int) -> List[int]:
    if not k or not nums: return []
        
    z = len(nums)
    
    if z <= k:  return [max(nums, default = 0)]

    q = deque([])
    res = []
    
    for i, num in enumerate(nums):
        if q and q[0] == i-k:
            q.popleft()
    
        while q and nums[q[-1]] < num:
            q.pop()
            
        q.append(i)
        if i >= k-1:  res.append(nums[q[0]])
    return res
   
# Since every num. enters and leaves the queue at most once, the time
# complexity is O(len(A)), independent of the value of K.
if __name__ == '__main__':
    B = [99,  74, 48, 27, 56, 88, 66, 77, 101]
    print(maxSliding(B, 3))

Answer 1

I don't see any obvious improvements to your algorithm.

Tests:

Your "main" section seems to be checking if the algorithm works, but you can make better use of the examples provided with the original prompt.

Constraints:

The original prompt makes certain promises about the inputs. It's reasonable to just take those as assumptions, or (maybe better, depending on stuff) to make them explicit assertions, but there's no need to handle violating cases.

Typing:

You've got type-hints in your function signature.
That's great!
But in python the idea of "types are comments that can't be wrong" only holds if you actually use a type-checker. Trying mypy on your code gives an error that it can't figure out the type of q. The easiest fix for this would be to use the Deque from typing (or upgrade to python 3.9) so you can write q = Deque[int]().

Begging for microseconds:

You can save yourself some conditional checks by changing how you handle the first couple rounds: Start the loop with something in the deque, and slice off the head of the result-list at the end. On the other hand, trying to optimize at that level of granularity is easy to get wrong. I banged out an over-engineered version, but without benchmarking this is worthless.

from typing import List, Deque, Iterable, Tuple, Callable
from itertools import islice

def _window_func(k: int, q: Deque[Tuple[int, int]]) -> Callable[[Tuple[int, int]], int]:
    def retval(pair):
        if q[0][0] == pair[0] - k:
            q.popleft()
        while q and q[-1][1] < pair[1]:
            q.pop()
        q.append(pair)
        return q[0][1]
    return retval

def maxSliding(nums: List[int], k: int) -> List[int]:
    assert nums
    assert 1 <= k <= len(nums)
    return list(islice(
        map(_window_func(k, Deque([(-1, nums[-1])])),
            enumerate(nums)),
        k - 1, None
    ))

tests = [([99,74,48,27,56,88,66,77,101], 3, [99,74,56,88,88,88,101]),
         ([1,3,-1,-3,5,3,6,7], 3, [3,3,5,5,6,7]),
         ([1], 1, [1]),
         ([1,-1], 1, [1,-1]),
         ([9,11], 2, [11]),
         ([4,-2], 2, [4])]

if __name__ == '__main__':
    for (l, k, result) in tests:
        try:
            actual = maxSliding(l, k)
            assert actual == result
        except:
            print(f'Offending test {(l, k, result)}, got {actual}')
            raise
    print("tests passed")
```