Today’s problem

https://leetcode.com/problems/product-of-the-last-k-numbers/description/

Intuition

  • Situation 1: if there is no 0: In this case, we can just use a prefix multiplication to do what the question asks.
  • Situation 2: if there is 0: Then it would be 0!

Therefore, all we need is to just check whether there is a 0 in the last k numbers of the stream. If yes, them just return 0.

Approach

  1. Use an array to store the multiplication prefix.
  2. Check whether there is a zero in the last k streams.

Complexity

  • Time complexity: $O(Q)$, Q means the number of operations.

  • Space complexity: $O(Q)$, Q means the number of operations.

Code

class ProductOfNumbers:

    def __init__(self):
        self.q = []
        self.mul = 1

    def add(self, num: int) -> None:
        self.mul *= num
        self.q.append(self.mul)
        if num == 0:
            self.q = []
            self.mul = 1

    def getProduct(self, k: int) -> int:
        if k > len(self.q):
            return 0
        if k == len(self.q):
            return self.mul
        return self.mul // self.q[-k - 1]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)

image.png