4
\$\begingroup\$

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))
\$\endgroup\$
7
  • \$\begingroup\$ This is a job for Numpy. Is there a specific reason you aren't using it? \$\endgroup\$
    – Reinderien
    Jan 2, 2021 at 18:51
  • \$\begingroup\$ The req. asked not to use any 3rd party library. Only Python's lib. Thanks! \$\endgroup\$
    – Daniel Hao
    Jan 2, 2021 at 18:54
  • \$\begingroup\$ Is the request a homework request? If so, please tag the question as such. \$\endgroup\$
    – Reinderien
    Jan 2, 2021 at 18:54
  • \$\begingroup\$ No, no, no - it's for practice on the Web site - to prepare for interview. I've solved it and seek for comments if any room for improvement. \$\endgroup\$
    – Daniel Hao
    Jan 2, 2021 at 18:55
  • \$\begingroup\$ Is it a particular interview practice website? Adding a link to the original question would be helpful. \$\endgroup\$
    – Reinderien
    Jan 2, 2021 at 18:56

1 Answer 1

2
\$\begingroup\$

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")
```
\$\endgroup\$
1
  • \$\begingroup\$ Hi, @ShapeOfMatter, thanks your review and feedback. I'll read and incorporate all the comments. Thank you again for effort. -Daniel \$\endgroup\$
    – Daniel Hao
    Jan 2, 2021 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.