Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Product of the Last K Numbers solution and explanation

MediumArrayData StreamDesignMath6 min read62.9% acceptanceUpdated 9 Apr 2026
Asked atStarbucksTargetTekionTiktokBytedanceGoogle
+5 moreMetaAppleAmazonMicrosoftBloomberg
Practise Product of the Last K Numbers
12:43
Leetcode 1352. Product of the Last K NumbersFraz · 12:43 · 8K viewsWatch on YouTube
9 more videos on this problem
  1. Leetcode 1352. Product of the Last K NumbersFraz · 12:43 · 8K views
  2. Product of the Last K Numbers | Brute Force | Follow Up Optimal | Leetcode 1352 | codestorywithMIKcodestorywithMIK · 28:12 · 7K views
  3. Product of the Last K Numbers | Leetcode 1352Techdose · 22:17 · 5K views
  4. PRODUCT OF THE LAST K NUMBERS | LEETCODE # 1352 | PYTHON SOLUTIONCracking FAANG · 11:05 · 2K views
  5. 1352. Product of the Last K Numbers | Leetcode Daily ChallengeEthos Typos · 13:56 · 2K views
  6. 1352. Product of the Last K Numbers | leetcode daily challenge | shashcode | java | dsa | shashwatShashCode · 12:57 · 2K views
  7. 1352. Product of the Last K Numbers | Prefix ProductsAryan Mittal · 17:42 · 1K views
  8. 1352. Product of the last K numbers | 🚀 Master Prefix Products Like a Pro!RAHUL VIJAYAN · 19:32 · 544 views
  9. Daily Leetcode #1781: Feb 14, 2025 - 1352. Product of the Last K NumbersProgramming Live with Larry · 21:38 · 504 views
  10. LeetCode 1352 Product of the Last K Numbers | Prefix Sum | Asked in Google MetaCode Harmony · 19:22 · 372 views

The problem

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.

Example:

Input
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

Output
[null,null,null,null,null,null,20,40,0,null,32]

Explanation
ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3);        // [3]
productOfNumbers.add(0);        // [3,0]
productOfNumbers.add(2);        // [3,0,2]
productOfNumbers.add(5);        // [3,0,2,5]
productOfNumbers.add(4);        // [3,0,2,5,4]
productOfNumbers.getProduct(2); // return 20. The product of the last 2 numbers is 5 * 4 = 20
productOfNumbers.getProduct(3); // return 40. The product of the last 3 numbers is 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // return 0. The product of the last 4 numbers is 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8);        // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // return 32. The product of the last 2 numbers is 4 * 8 = 32

Constraints:

  • 0 <= num <= 100
  • 1 <= k <= 4 * 104
  • At most 4 * 104 calls will be made to add and getProduct.
  • The product of the stream at any point in time will fit in a 32-bit integer.

Approach overview

Problem Overview: Design a data structure that supports two operations on a stream of integers: add(num) and getProduct(k). The second operation returns the product of the last k numbers added to the stream. The challenge is answering queries efficiently even when the stream grows large.

Approach 1: Naive Approach with Array (Add: O(1), Query: O(k) time, O(n) space)

Store every incoming number in a dynamic array. When getProduct(k) is called, iterate over the last k elements and multiply them together. The logic is straightforward: compute the product on demand using a simple loop from n - k to n - 1. This approach uses an array to keep the stream and requires no preprocessing.

The downside appears when queries are frequent or k becomes large. Each query scans up to k elements, making the worst‑case time O(k). For a long stream with many queries, this quickly becomes inefficient. Still, it works well for small inputs or when query frequency is low.

Approach 2: Prefix Products (Add: O(1), Query: O(1) time, O(n) space)

The optimized solution stores cumulative prefix products. Maintain a list where prefix[i] represents the product of all numbers from the start of the stream up to index i. When a new number arrives, append prefix[last] * num. To compute the product of the last k numbers, divide the current prefix product by the prefix value k positions earlier.

The key complication is handling zeros. If a zero appears in the stream, any product spanning that position becomes zero. The fix is simple: reset the prefix list whenever a zero is added. If the query asks for more elements than currently stored after the last zero, return 0.

This design transforms each query into constant time arithmetic. It works because multiplication over a range can be reconstructed from two prefix values, similar to prefix sums but using products. The pattern commonly appears in math and data stream problems where repeated range queries must be fast.

Recommended for interviews: Interviewers expect the prefix product approach. The brute force array method demonstrates baseline reasoning, but the optimized design shows you recognize prefix techniques and can adapt them to streaming data with edge cases like zeros. Achieving O(1) query time is the key signal of a strong solution.

Approach 1: Naive Approach with Array

In this approach, we maintain an array that stores all elements added so far. When retrieving the product of the last k elements, we iterate from the end of the array, multiplying the last k elements to compute the result. This approach can be simple but may lead to more complex implementations and inefficient performance for large values of k.

class ProductOfNumbers:
    def __init__(self):
        self.nums = []

    def add(self, num: int) -> None:
        self.nums.append(num)

    def getProduct(self, k: int) -> int:
        product = 1
        for i in range(len(self.nums) - k, len(self.nums)):
            product *= self.nums[i]
        return product

# Example usage:
productOfNumbers = ProductOfNumbers()
productOfNumbers.add(3)
productOfNumbers.add(0)
productOfNumbers.add(2)
productOfNumbers.add(5)
productOfNumbers.add(4)
print(productOfNumbers.getProduct(2)) # Output: 20
print(productOfNumbers.getProduct(3)) # Output: 40
print(productOfNumbers.getProduct(4)) # Output: 0
productOfNumbers.add(8)
print(productOfNumbers.getProduct(2)) # Output: 32
import java.util.ArrayList;

class ProductOfNumbers {
    ArrayList<Integer> nums;

    public ProductOfNumbers() {
        nums = new ArrayList<Integer>();
    }

    public void add(int num) {
        nums.add(num);
    }

    public int getProduct(int k) {
        int product = 1;
        for (int i = nums.size() - k; i < nums.size(); i++) {
            product *= nums.get(i);
        }
        return product;
    }

    public static void main(String[] args) {
        ProductOfNumbers productOfNumbers = new ProductOfNumbers();
        productOfNumbers.add(3);
        productOfNumbers.add(0);
        productOfNumbers.add(2);
        productOfNumbers.add(5);
        productOfNumbers.add(4);
        System.out.println(productOfNumbers.getProduct(2)); // Output: 20
        System.out.println(productOfNumbers.getProduct(3)); // Output: 40
        System.out.println(productOfNumbers.getProduct(4)); // Output: 0
        productOfNumbers.add(8);
        System.out.println(productOfNumbers.getProduct(2)); // Output: 32
    }
}
#include <vector>

class ProductOfNumbers {
    std::vector<int> nums;
public:
    void add(int num) {
        nums.push_back(num);
    }

    int getProduct(int k) {
        int product = 1;
        for (int i = nums.size() - k; i < nums.size(); ++i) {
            product *= nums[i];
        }
        return product;
    }
};

int main() {
    ProductOfNumbers productOfNumbers;
    productOfNumbers.add(3);
    productOfNumbers.add(0);
    productOfNumbers.add(2);
    productOfNumbers.add(5);
    productOfNumbers.add(4);
    productOfNumbers.getProduct(2); // Output: 20
    productOfNumbers.getProduct(3); // Output: 40
    productOfNumbers.getProduct(4); // Output: 0
    productOfNumbers.add(8);
    productOfNumbers.getProduct(2); // Output: 32
}
class ProductOfNumbers {
  constructor() {
    this.nums = [];
  }

  add(num) {
    this.nums.push(num);
  }

  getProduct(k) {
    let product = 1;
    for (let i = this.nums.length - k; i < this.nums.length; i++) {
      product *= this.nums[i];
    }
    return product;
  }
}

// Example usage:
const productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3);
productOfNumbers.add(0);
productOfNumbers.add(2);
productOfNumbers.add(5);
productOfNumbers.add(4);
console.log(productOfNumbers.getProduct(2)); // Output: 20
console.log(productOfNumbers.getProduct(3)); // Output: 40
console.log(productOfNumbers.getProduct(4)); // Output: 0
productOfNumbers.add(8);
console.log(productOfNumbers.getProduct(2)); // Output: 32
#include <stdio.h>

int nums[40000];
int addIndex = 0;

void add(int num) {
    nums[addIndex++] = num;
}

int getProduct(int k) {
    int product = 1;
    for (int i = addIndex - 1; i >= addIndex - k; i--) {
        product *= nums[i];
    }
    return product;
}

void tester() {
    add(3);
    add(0);
    add(2);
    add(5);
    add(4);
    printf("%d\n", getProduct(2)); // Output: 20
    printf("%d\n", getProduct(3)); // Output: 40
    printf("%d\n", getProduct(4)); // Output: 0
    add(8);
    printf("%d\n", getProduct(2)); // Output: 32
}
using System;
using System.Collections.Generic;

public class ProductOfNumbers {
    private List<int> nums;

    public ProductOfNumbers() {
        nums = new List<int>();
    }

    public void Add(int num) {
        nums.Add(num);
    }

    public int GetProduct(int k) {
        int product = 1;
        for (int i = nums.Count - k; i < nums.Count; i++) {
            product *= nums[i];
        }
        return product;
    }

    public static void Main(string[] args) {
        ProductOfNumbers productOfNumbers = new ProductOfNumbers();
        productOfNumbers.Add(3);
        productOfNumbers.Add(0);
        productOfNumbers.Add(2);
        productOfNumbers.Add(5);
        productOfNumbers.Add(4);
        Console.WriteLine(productOfNumbers.GetProduct(2)); // Output: 20
        Console.WriteLine(productOfNumbers.GetProduct(3)); // Output: 40
        Console.WriteLine(productOfNumbers.GetProduct(4)); // Output: 0
        productOfNumbers.Add(8);
        Console.WriteLine(productOfNumbers.GetProduct(2)); // Output: 32
    }
}

This Python solution uses a list to store all added numbers. The getProduct function iterates from the last k elements and computes their product. The space complexity is O(n) due to the storage requirement, and the time complexity is O(k) for the getProduct function.

Complexity

Time Complexity: O(k).
Space Complexity: O(n).

Try this approach in the editor

Approach 2: Optimized Approach with Prefix Products

To enhance efficiency, we calculate prefix products of the stream. Instead of storing all numbers, we store the cumulative product up to each index. Each time a zero is added, we reset these products because it invalidates previous products for future calculations. This allows us to retrieve the product of the last k numbers in constant time.

class ProductOfNumbers:
    def __init__(self):
        self.products = [1]

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

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

# Example usage:
productOfNumbers = ProductOfNumbers()
productOfNumbers.add(3)
productOfNumbers.add(0)
productOfNumbers.add(2)
productOfNumbers.add(5)
productOfNumbers.add(4)
print(productOfNumbers.getProduct(2)) # Output: 20
print(productOfNumbers.getProduct(3)) # Output: 40
print(productOfNumbers.getProduct(4)) # Output: 0
productOfNumbers.add(8)
print(productOfNumbers.getProduct(2)) # Output: 32
import java.util.ArrayList;

class ProductOfNumbers {
    ArrayList<Integer> products;

    public ProductOfNumbers() {
        products = new ArrayList<Integer>();
        products.add(1);
    }

    public void add(int num) {
        if (num == 0) {
            products.clear();
            products.add(1);
        } else {
            products.add(products.get(products.size() - 1) * num);
        }
    }

    public int getProduct(int k) {
        if (k >= products.size()) return 0;
        return products.get(products.size() - 1) / products.get(products.size() - k - 1);
    }

    public static void main(String[] args) {
        ProductOfNumbers productOfNumbers = new ProductOfNumbers();
        productOfNumbers.add(3);
        productOfNumbers.add(0);
        productOfNumbers.add(2);
        productOfNumbers.add(5);
        productOfNumbers.add(4);
        System.out.println(productOfNumbers.getProduct(2)); // Output: 20
        System.out.println(productOfNumbers.getProduct(3)); // Output: 40
        System.out.println(productOfNumbers.getProduct(4)); // Output: 0
        productOfNumbers.add(8);
        System.out.println(productOfNumbers.getProduct(2)); // Output: 32
    }
}
#include <vector>

class ProductOfNumbers {
    std::vector<int> products;
public:
    ProductOfNumbers() {
        products.push_back(1);
    }

    void add(int num) {
        if (num == 0) {
            products = {1};
        } else {
            products.push_back(products.back() * num);
        }
    }

    int getProduct(int k) {
        if (k >= products.size()) return 0;
        return products.back() / products[products.size() - k - 1];
    }
};

int main() {
    ProductOfNumbers productOfNumbers;
    productOfNumbers.add(3);
    productOfNumbers.add(0);
    productOfNumbers.add(2);
    productOfNumbers.add(5);
    productOfNumbers.add(4);
    productOfNumbers.getProduct(2); // Output: 20
    productOfNumbers.getProduct(3); // Output: 40
    productOfNumbers.getProduct(4); // Output: 0
    productOfNumbers.add(8);
    productOfNumbers.getProduct(2); // Output: 32
}
class ProductOfNumbers {
  constructor() {
    this.products = [1];
  }

  add(num) {
    if (num === 0) {
      this.products = [1];
    } else {
      this.products.push(this.products[this.products.length - 1] * num);
    }
  }

  getProduct(k) {
    if (k >= this.products.length) return 0;
    return this.products[this.products.length - 1] / this.products[this.products.length - k - 1];
  }
}

// Example usage:
const productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3);
productOfNumbers.add(0);
productOfNumbers.add(2);
productOfNumbers.add(5);
productOfNumbers.add(4);
console.log(productOfNumbers.getProduct(2)); // Output: 20
console.log(productOfNumbers.getProduct(3)); // Output: 40
console.log(productOfNumbers.getProduct(4)); // Output: 0
productOfNumbers.add(8);
console.log(productOfNumbers.getProduct(2)); // Output: 32
#include <stdio.h>
int products[40002];
int size = 1;
products[0] = 1;

void add(int num) {
    if (num == 0) {
        products[size] = 1;
        size = 1;
    } else {
        products[size] = products[size - 1] * num;
        size++;
    }
}

int getProduct(int k) {
    if (k >= size) return 0;
    return products[size - 1] / products[size - k - 1];
}

void tester() {
    add(3);
    add(0);
    add(2);
    add(5);
    add(4);
    printf("%d\n", getProduct(2)); // Output: 20
    printf("%d\n", getProduct(3)); // Output: 40
    printf("%d\n", getProduct(4)); // Output: 0
    add(8);
    printf("%d\n", getProduct(2)); // Output: 32
}
using System;
using System.Collections.Generic;

public class ProductOfNumbers {
    private List<int> products;

    public ProductOfNumbers() {
        products = new List<int>();
        products.Add(1);
    }

    public void Add(int num) {
        if (num == 0) {
            products.Clear();
            products.Add(1);
        } else {
            products.Add(products[products.Count - 1] * num);
        }
    }

    public int GetProduct(int k) {
        if (k >= products.Count) return 0;
        return products[products.Count - 1] / products[products.Count - k - 1];
    }

    public static void Main(string[] args) {
        ProductOfNumbers productOfNumbers = new ProductOfNumbers();
        productOfNumbers.Add(3);
        productOfNumbers.Add(0);
        productOfNumbers.Add(2);
        productOfNumbers.Add(5);
        productOfNumbers.Add(4);
        Console.WriteLine(productOfNumbers.GetProduct(2)); // Output: 20
        Console.WriteLine(productOfNumbers.GetProduct(3)); // Output: 40
        Console.WriteLine(productOfNumbers.GetProduct(4)); // Output: 0
        productOfNumbers.Add(8);
        Console.WriteLine(productOfNumbers.GetProduct(2)); // Output: 32
    }
}

Python's solution manages prefix products in a list. Encountering zero results in product list resetting. Via division, product retrieval is quick, providing O(1) efficiency at O(n) space expense.

Complexity

Time Complexity: O(1).
Space Complexity: O(n).

Try this approach in the editor

Approach 3: Prefix Product

We initialize an array s, where s[i] represents the product of the first i numbers.

When calling add(num), we judge whether num is 0. If it is, we set s to [1]. Otherwise, we multiply the last element of s by num and add the result to the end of s.

When calling getProduct(k), we now judge whether the length of s is less than or equal to k. If it is, we return 0. Otherwise, we return the last element of s divided by the k + 1th element from the end of s. That is, s[-1] / s[-k - 1].

The time complexity is O(1), and the space complexity is O(n). Where n is the number of times add is called.

class ProductOfNumbers {
    s = [1];

    add(num: number): void {
        if (num === 0) {
            this.s = [1];
        } else {
            const i = this.s.length;
            this.s[i] = this.s[i - 1] * num;
        }
    }

    getProduct(k: number): number {
        const i = this.s.length;
        if (k > i - 1) return 0;
        return this.s[i - 1] / this.s[i - k - 1];
    }
}
type ProductOfNumbers struct {
	s []int
}

func Constructor() ProductOfNumbers {
	return ProductOfNumbers{[]int{1}}
}

func (this *ProductOfNumbers) Add(num int) {
	if num == 0 {
		this.s = []int{1}
		return
	}
	this.s = append(this.s, this.s[len(this.s)-1]*num)
}

func (this *ProductOfNumbers) GetProduct(k int) int {
	n := len(this.s)
	if n <= k {
		return 0
	}
	return this.s[len(this.s)-1] / this.s[len(this.s)-k-1]
}

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(num);
 * param_2 := obj.GetProduct(k);
 */
Try this approach in the editor

Complexity comparison

ApproachComplexity
Naive Approach with Array

Time Complexity: O(k).
Space Complexity: O(n).

Optimized Approach with Prefix Products

Time Complexity: O(1).
Space Complexity: O(n).

Prefix Product–

Complexity analysis

ApproachTimeSpaceWhen to Use
Naive Array MultiplicationAdd: O(1), Query: O(k)O(n)Useful for small streams or when query operations are rare
Prefix Products with Zero ResetAdd: O(1), Query: O(1)O(n)Best for frequent queries and large data streams

Frequently asked questions

Is Product of the Last K Numbers easy or hard?

Product of the Last K Numbers is rated Medium difficulty. The challenge is recognizing that naive multiplication is too slow and switching to prefix products while correctly handling zeros in the stream.

Product of the Last K Numbers Python/Java solution

Both Python and Java implementations follow the same prefix product strategy. Maintain a list of cumulative products and reset it whenever a zero appears. The getProduct method returns the division of prefix values or zero if the query crosses a zero boundary.

How to solve Product of the Last K Numbers in O(1)?

Store cumulative prefix products. When a new number arrives, multiply it with the previous prefix and append it to the list. To compute the last k product, divide the current prefix value by the prefix value k steps earlier. Reset the prefix list when a zero appears to handle zero-containing ranges.

What is the best approach for Product of the Last K Numbers?

The prefix product approach is the most efficient. Maintain a running list of cumulative products and compute the product of the last k numbers by dividing two prefix values. With proper handling of zeros by resetting the prefix array, both add and query operations run in O(1) time.

Is Product of the Last K Numbers asked at Google/Amazon/Meta?

Product of the Last K Numbers appears in interview preparation sets for companies that test data structure design and streaming data problems, including Google and Amazon style interviews. It evaluates understanding of prefix techniques and edge cases like zero handling.

What data structure is used in Product of the Last K Numbers?

The core data structure is a dynamic array storing prefix products. The design behaves like a lightweight data stream processor where each element updates cumulative state. Arithmetic division between prefix values allows constant-time range product queries.

What is the time complexity of Product of the Last K Numbers?

The optimal solution runs in O(1) time for both add and getProduct operations using prefix products. Space complexity is O(n) because the structure stores prefix values for the stream since the last zero. The naive approach requires O(k) time per query.

Comments

Now write it yourselfClose this page and solve Product of the Last K Numbers in the editor, without looking.
Practise Product of the Last K Numbers