Product of the Last K Numbers — Editorial

Opening the reading…

Intuitionturning a product query into a prefix-product ratio

For a stream without zero, the product of the last k values is the product of the whole stream divided by the product before those k values. A prefix-product array stores exactly those cumulative products, so the answer is prefix[n] / prefix[n - k]. Each nonzero add extends the array by one multiplication, and each query uses two existing entries.

Zero is the one value that prevents division from working: every prefix after it would be zero, and dividing two such prefixes would lose the product you need. Instead, zero starts a new independent suffix. Keep a leading 1 for that suffix. If a query asks for at least as many values as the suffix contains, the requested range includes the zero and the answer is zero; otherwise both prefix entries belong to the same zero-free suffix.

Approachone invariant handles both add and getProduct

Start each ProductOfNumbers operation with prefix containing one value, 1. This sentinel represents the empty prefix and makes the product of the first stored number equal to prefix[1] / prefix[0] without a special case.

For add with a nonzero num, append prefix.back() * num. The new last entry is the product of every value in the current zero-free suffix, so future queries can subtract the earlier prefix through division.

For add with num equal to zero, replace prefix with {1}. Any range reaching this zero has product zero, while ranges after it can be answered independently; retaining old prefixes would make the index test and division describe different segments.

For getProduct(k), check whether k is at least prefix.size(). The stored suffix has prefix.size() - 1 numbers, so this condition means the requested range reaches the most recent zero and its product is zero.

If the zero check fails, divide prefix.back() by prefix[prefix.size() - 1 - k]. The denominator is the product before the last k stored values, and cancelling it leaves exactly those k values.

For each operation, append the required textual result: null for construction and add, and the computed integer converted to a string for getProduct. This preserves the output order of the command stream.

Complexityconstant work per operation after linear storage

MEASURE	BOUND	WHY
Time	O(1) per command, O(q) total	An add performs one reset or one multiplication, and a getProduct performs one size check and one division. No command scans earlier values, so q commands contribute a constant amount of work each.
Space	O(n) extra	The prefix array stores one entry for each value since the most recent zero, plus the sentinel. The returned result vector is required output and is excluded from the extra-space bound. In the worst case no zero appears, so n grows to the full stream length; a zero can reduce the stored suffix to size zero.

Here n is the maximum number of values in the current zero-free suffix, and q is the total number of commands processed.

Annotated solutionC++ · command-stream adapter · complete judge-shaped implementation

CPPMaintain prefix products for the current zero-free suffix and answer each query by division.

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    static vector<string> process(vector<string>& commands,
                                  vector<vector<int>>& args) {
        vector<string> result;
        vector<int> prefix = {1};

        for (int i = 0; i < static_cast<int>(commands.size()); ++i) {
            if (commands[i] == "ProductOfNumbers") {
                prefix = {1};
                result.push_back("null");
            } else if (commands[i] == "add") {
                int num = args[i][0];

                if (num == 0) {
                    prefix = {1};
                } else {
                    prefix.push_back(prefix.back() * num);
                }

                result.push_back("null");
            } else if (commands[i] == "getProduct") {
                int k = args[i][0];

                if (k >= static_cast<int>(prefix.size())) {
                    result.push_back("0");
                } else {
                    int beforeLastK = static_cast<int>(prefix.size()) - 1 - k;
                    int answer = prefix.back() / prefix[beforeLastK];
                    result.push_back(to_string(answer));
                }
            }
        }

        return result;
    }
};

The index expression prefix.size() - 1 - k is the important placement detail. prefix.size() - 1 counts stored numbers, because the first entry is only the sentinel. Moving back k numbers therefore lands at the prefix immediately before the requested range. The zero check must happen first, because a range that crosses the reset boundary has no valid denominator in the current prefix array.