[Python][LeetCode] 1825. Finding MK Average

Link

from sortedcontainers import SortedList
from collections import deque

class MKAverage:
    def __init__(self, m: int, k: int):
        # Initialize the 'm' and 'k'. 
        # Each means 'size of the stream' and 'the number of excluded elements.
        self.m = m
        self.k = k
        # Imported 'SortedList' will make the stream 'sorted'.
        self.sl = SortedList()

        # deque is kind of the list for accessing both side of the list.
        # Whenever you use working kind of 'enqueue' or 'dequeue' process,
        # it could be  better to use it.
        self.q = deque()

    def addElement(self, num: int) -> None:
        # If queue has 'm' elements, and you want to add 'new' element in the q,
        # the most 'old' element must be deleted.
        if len(self.q) == self.m:
            # the if statement's content means the process of it.
            old = self.q.popleft()
            self.sl.remove(old)

        # The default process is appending 'num' in the both of 'q' and 'sl'.
        self.q.append(num)
        self.sl.add(num)

    def calculateMKAverage(self) -> int:
        # If 'sl' doens't have enough number of elements of 'm', then It can't be worked. 
        # So It returns '-1' as you can see in the problem's 'condition'.
        if len(self.sl) < self.m:
            return -1
        total = sum(self.sl[self.k:self.m-self.k])
        # the index of scope for sum is from 'k' to 'm-k-1'.
        return total // (self.m - 2*self.k)

Summary.

1. You can know ‘SortedList’ method in this problem. It can be compared to ‘sort’ method of ‘built-in’. By the way , ‘SortedList’ is used in the condition of ‘often changed condition’, and it has average time complexity of O(N). However, ‘sort’ has average time complexity of O(N), but it has O(NlogN) in the worst case.
2. In the definition of ‘addElement’, there is no ‘return’. I think the ‘test case’ sector in that webpage has ‘print’. So, I think we don’t have to be care about the fact that ‘there is no ‘return’ in the definition’.