D
DevExCode

LeetCode 1352: Product of the Last K Numbers Solution

Master LeetCode problem 1352 (Product of the Last K Numbers), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1352. Product of the Last K Numbers

Medium
ArrayMathDesignData StreamPrefix Sum

Problem Explanation

Explanation

To solve this problem efficiently, we can maintain two lists:

  1. prefixProducts: A list to store the prefix products of the stream.
  2. stream: A list to store the stream of integers.

When a new integer is added to the stream, we update both lists accordingly. To calculate the product of the last k numbers efficiently, we divide the last prefix product by the prefix product k steps before the end of the list.

Algorithm:

  1. Initialize prefixProducts with a single element 1.
  2. Initialize an empty list stream.
  3. When add(num) is called:
    • If num is 0, clear both prefixProducts and stream.
    • Otherwise, update the prefixProducts list by multiplying the last element with num.
    • Append num to the stream.
  4. When getProduct(k) is called:
    • Get the last element of prefixProducts and the element k steps before the end.
    • Return the division of the last element by the k steps before element.

Time Complexity:

  • Adding a number: O(1)
  • Getting product of last k numbers: O(1)

Space Complexity:

  • O(n) where n is the total number of elements added to the stream.

Solution Code

class ProductOfNumbers {
    List<Integer> prefixProducts;
    List<Integer> stream;

    public ProductOfNumbers() {
        prefixProducts = new ArrayList<>();
        prefixProducts.add(1);
        stream = new ArrayList<>();
    }

    public void add(int num) {
        if (num == 0) {
            prefixProducts = new ArrayList<>();
            prefixProducts.add(1);
            stream = new ArrayList<>();
        } else {
            prefixProducts.add(prefixProducts.get(prefixProducts.size() - 1) * num);
            stream.add(num);
        }
    }

    public int getProduct(int k) {
        int n = stream.size();
        return prefixProducts.get(n) / prefixProducts.get(n - k - 1);
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1352 (Product of the Last K Numbers)?

This page provides optimized solutions for LeetCode problem 1352 (Product of the Last K Numbers) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1352 (Product of the Last K Numbers)?

The time complexity for LeetCode 1352 (Product of the Last K Numbers) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1352 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1352 in Java, C++, or Python.

Back to LeetCode Solutions