JZ 59 I & II | LC 239

Queue
Queue
Publish Date:   2022-01-09

Solutions to JZ 59 I (same as LeetCode 239 Sliding Window Maximum) & II.

JZ 59 I | LeetCode 239

Find the maximum value of every sliding window of an array (Hard). [NowCoder link] [LeetCode link]

This problem requires time complexity O(n) and space complexity O(n). According to the usual solution, if the length of array is n, the size of window is k, there should be (n - k +1) windows. So the time complexity is O((n - k + 1) * k) = O(nk). This is not ideal, we have to find a way to avoid finding max value by linear iteration through each window.

We can use Queue data structure to help get max value for each window. We have to make sure the deque: 1) when the value popped out of the window is the max value in deque, delete it from deque, 2) keep deque decreasing. In this way, for each window, the max value is the first value in deque. Now time complexity is O(n) where n is the length of nums, space complexity is O(k) where k is the size of windows. 

import collections
class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        deque = collections.deque()
        res, n = [], len(num)
        if size == 0:
            return res
          
        for i, j in zip(range(1-size, n + 1 - size), range(n)):
            if i > 0 and deque[0] == num[i-1]: 
                deque.popleft() # delete the max value when the max value moves out of the window
            while deque and deque[-1] < num[j]: 
                deque.pop() # keep deque decreasing
            deque.append(num[j]) # append the next value 
            if i >= 0:
                res.append(deque[0]) # append the max value of that window
        return res

Note: pop() deletes value from the right, which is used for stack. pop(0) equals to popleft() which is used for queue. append() equals to push() which adds value from the right.

JZ 59 II

Implement a function max_value() to find the maximum value of an array (Medium). [link]

We keep a Queue with decreasing values. It is updated when pushing or popping so that the first value is always the max value. The idea is “pay space to buy time”. The operations (pop, push, popleft) are all O(1) so the time complexity becomes O(1), the space complexity is O(n).

Note that the deque has two updating rules: 1) when push_back() a new value that is larger, the deque need to pop out all smaller values to keep the deque decreasing. 2) when pop_front(), if the value popped out is the largest, deque need to pop out that value too.

import queue
class MaxQueue:

    def __init__(self):
        self.queue = queue.Queue()
        self.deque = queue.deque()

    def max_value(self) -> int:
        return self.deque[0] if self.deque else -1

    def push_back(self, value: int) -> None:
        self.queue.put(value) # Queue object has no append(), but put()
        while self.deque and self.deque[-1] < value:
            self.deque.pop()
        self.deque.append(value)

    def pop_front(self) -> int:
        if self.queue.empty():
            return -1
        val = self.queue.get() # Queue object has no popleft() but get()
        if val == self.deque[0]:
            self.deque.popleft()
        return val
Queue
  TOC