How do you solve Product of the Last K Numbers on LeetCode?

Product of the Last K Numbers (LeetCode #1352) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a prefix product array allows for efficient retrieval of products over a range.

What is the brute force solution for Product of the Last K Numbers?

The brute force approach for Product of the Last K Numbers is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute-force approach calculates the product of the last k numbers each time we need it. This means we will iterate through the last k elements every time we call getProduct, which is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Product of the Last K Numbers?

Product of the Last K Numbers uses the following concepts: Array, Math, Design, Data Stream, Prefix Sum. The recommended patterns to study are: Prefix Sum, Dynamic Programming.

What are the interview tips for Product of the Last K Numbers?

Always consider edge cases, especially when dealing with streams or dynamic data. Explain your thought process clearly, especially when transitioning from brute force to optimal solutions. Practice writing clean and efficient code, as readability matters in interviews.

What are common mistakes when solving Product of the Last K Numbers?

Not resetting the state when a zero is added, leading to incorrect product calculations. Forgetting to handle edge cases like k being larger than the current list size.

#1352

Product of the Last K Numbers

Medium

ArrayMathDesignData StreamPrefix SumPrefix SumDynamic Programming

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a prefix product array to store cumulative products, allowing us to compute the product of the last k numbers in constant time. This is efficient and avoids recalculating products repeatedly.

⚙️

Algorithm

3 steps

1Step 1: Maintain a list to store the stream of numbers and a prefix product list.
2Step 2: When adding a number, append it to the numbers list and update the prefix product list appropriately.
3Step 3: To get the product of the last k numbers, return the product using the prefix product list.

solution.py17 lines

1class ProductOfNumbers:
2    def __init__(self):
3        self.numbers = []
4        self.prefix_products = [1]
5
6    def add(self, num: int) -> None:
7        if num == 0:
8            self.numbers = []
9            self.prefix_products = [1]
10        else:
11            self.numbers.append(num)
12            self.prefix_products.append(self.prefix_products[-1] * num)
13
14    def getProduct(self, k: int) -> int:
15        if k > len(self.numbers):
16            return 0
17        return self.prefix_products[-1] // self.prefix_products[-k - 1]

ℹ

Complexity note: The time complexity is O(n) for the add operation since we may need to update the prefix product list. The getProduct operation is O(1) because we can retrieve the product using precomputed values. The space complexity is O(n) for storing the numbers and prefix products.

1Using a prefix product array allows for efficient retrieval of products over a range.
2Handling zeros in the stream requires resetting the state to avoid incorrect calculations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.