1352. Product of the Last K Numbers

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/product-of-the-last-k-numbers
• topics: Prefix Sum

Description

Design an algorithm that accepts a stream of integers and retrieves the product of the last k integers of the stream.

Implement the ProductOfNumbers class:

• ProductOfNumbers() Initializes the object with an empty stream.
• void add(int num) Appends the integer num to the stream.
• int getProduct(int k) Returns the product of the last k numbers in the current list. You can assume that always the current list has at least k numbers.

The test cases are generated so that, at any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.

Idea

• Prefix sums and handle 0 case

Code

class ProductOfNumbers:
    def __init__(self):
        self.products = [1]
 
    def add(self, num: int) -> None:
        if num == 0:
            self.products.clear()
        else:
            self.products.append(num)
            if len(self.products) > 1:
                self.products[-1] *= self.products[-2]
 
    def getProduct(self, k: int) -> int:
        if len(self.products) < k:
            return 0
        if len(self.products) == k:
            return self.products[-1]
        
        return int(self.products[-1] / self.products[-k-1])