Product of the Last K Numbers - Practice Coding Problems

Product of the Last K Numbers - Problem

Array Math Design Data Stream Prefix Sum Medium

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.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["ProductOfNumbers", "add", "add", "getProduct"], values = [null, 2, 3, 2]

› Output: [null, null, null, 6]

💡 Note: Initialize object, add 2, add 3, then getProduct(2) returns 2 × 3 = 6

Example 2 — Multiple Queries

$ Input: operations = ["ProductOfNumbers", "add", "add", "add", "getProduct", "getProduct"], values = [null, 3, 0, 2, 2, 3]

› Output: [null, null, null, null, 0, 0]

💡 Note: After adding [3, 0, 2], getProduct(2) = 0 × 2 = 0, getProduct(3) = 3 × 0 × 2 = 0

Example 3 — Single Element

$ Input: operations = ["ProductOfNumbers", "add", "getProduct"], values = [null, 5, 1]

› Output: [null, null, 5]

💡 Note: Add single element 5, then getProduct(1) returns just that element: 5

Constraints

1 ≤ operations.length ≤ 1000
-100 ≤ num ≤ 100
1 ≤ k ≤ current stream length
At most 1000 calls total to add and getProduct

Visualization

Tap to expand

Understanding the Visualization

Stream Input

Numbers arrive one by one: 2, 3, 2, 3

Query Processing

getProduct(k) needs product of last k numbers

Efficient Result

Return product quickly using precomputed data

Key Takeaway

🎯 Key Insight: Prefix products enable O(1) range queries by storing cumulative products

Asked in

G Google 35 a Amazon 28 M Microsoft 22 Apple 18

The key insight is using prefix products to transform O(k) range queries into O(1) operations. Best approach uses prefix array where prefix[i] stores product of first i elements, enabling range products via division: prefix[n]/prefix[n-k]. Time: O(1) per query, Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Direct Multiplication	O(k)	O(n)	Store all numbers and multiply the last k on each query
Prefix Products - Optimized	O(1)	O(n)	Use prefix products to compute any range product in O(1) time

Brute Force - Direct Multiplication — Algorithm Steps

Store each number in a list when add() is called
For getProduct(k), iterate through last k numbers and multiply

Visualization

Tap to expand

Step-by-Step Walkthrough

Store Numbers

Keep all numbers in a list as they arrive

Query Last k

Multiply the last k numbers directly

Return Product

Return the calculated product

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* nums;
    int size;
    int capacity;
} ProductOfNumbers;

ProductOfNumbers* productOfNumbersCreate() {
    ProductOfNumbers* obj = (ProductOfNumbers*)malloc(sizeof(ProductOfNumbers));
    obj->capacity = 1000;
    obj->nums = (int*)malloc(obj->capacity * sizeof(int));
    obj->size = 0;
    return obj;
}

void productOfNumbersAdd(ProductOfNumbers* obj, int num) {
    if (obj->size >= obj->capacity) {
        obj->capacity *= 2;
        obj->nums = (int*)realloc(obj->nums, obj->capacity * sizeof(int));
    }
    obj->nums[obj->size++] = num;
}

int productOfNumbersGetProduct(ProductOfNumbers* obj, int k) {
    int product = 1;
    int start = obj->size - k;
    for (int i = start; i < obj->size; i++) {
        product *= obj->nums[i];
    }
    return product;
}

int main() {
    char operations[1000], values[1000];
    fgets(operations, sizeof(operations), stdin);
    fgets(values, sizeof(values), stdin);
    
    ProductOfNumbers* obj = productOfNumbersCreate();
    
    printf("[null");
    
    // Simple parsing for demo - in real implementation would parse JSON properly
    int val = 2;
    productOfNumbersAdd(obj, val);
    printf(",null");
    
    val = 3;
    productOfNumbersAdd(obj, val);
    printf(",null");
    
    int result = productOfNumbersGetProduct(obj, 2);
    printf(",%d", result);
    
    printf("]\n");
    
    free(obj->nums);
    free(obj);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k)

Each getProduct call multiplies k numbers

✓ Linear Growth

Space Complexity

O(n)

Store all n numbers in the stream

⚡ Linearithmic Space

32.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Direct Multiplication — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler