Problem Statement
Brute Force [TLE]
class ProductOfNumbers:
def __init__(self):
self.stack = []
def add(self, num: int) -> None:
self.stack.append(num)
def getProduct(self, k: int) -> int:
res = 1
n = len(self.stack)
for i in range(k):
res *= self.stack[n - i - 1]
return res
# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)
My Solution
class ProductOfNumbers:
def __init__(self):
self.arr = []
self.prefix = 1
self.length = 0
def add(self, num: int) -> None:
if num == 0:
self.prefix = 1
self.arr = []
self.length = 0
return
self.prefix *= num
self.arr.append(self.prefix)
self.length += 1
def getProduct(self, k: int) -> int:
if self.length == k:
return self.arr[-1]
if k > self.length:
return 0
return self.arr[-1] // self.arr[self.length - k - 1]
# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)
Editorial
Approach: Prefix Product
class ProductOfNumbers:
# Stores cumulative product of the stream
def __init__(self):
# Initialize the product list with 1 to handle multiplication logic
self.prefix_product = [1]
self.size = 0
def add(self, num: int):
if num == 0:
# If num is 0, reset the cumulative products since multiplication
# with 0 invalidates previous products
self.prefix_product = [1]
self.size = 0
else:
# Append the cumulative product of the current number with the last
# product
self.prefix_product.append(self.prefix_product[self.size] * num)
self.size += 1
def getProduct(self, k: int) -> int:
# Check if the requested product length exceeds the size of the valid
# product list
if k > self.size:
return 0
# Compute the product of the last k elements using division
return (
self.prefix_product[self.size] // self.prefix_product[self.size - k]
)
