Algorithms to Compute the Sliding Window Product

Implement a data structure with the following methods:

• SlidingWindowProduct() constructs a new instance.
• add(int num) adds the number num to the data structure.
• product(int k) returns the product of the last k numbers.

Constraints
n ≤ 100,000 where n is the number of calls to add and product.
Example 1
Input
methods = [“constructor”, “add”, “add”, “product”, “add”, “product”]
arguments = [[], [2], [3], [2], [4], [3]]`
Output
[null, null, null, 6, null, 24]

Explanation
s = SlidingWindowProduct()
s.add(2)
s.add(3)
s.product(2) == 6
s.add(4)
s.product(3) == 24

Bruteforce Algorithm to Compute the Sliding Window Product

We can just keep a simple source of truth – the numbers, and compute the product when we want – this takes O(N) time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class SlidingWindowProduct {
    public:
    SlidingWindowProduct() {
 
    }
 
    void add(int num) {
        data.push_back(num);
    }
 
    int product(int k) {
        int s = 1;
        for (int i = 0; i < k; ++ i) {
            s *= data[data.size() - i - 1];
            if (s == 0) return s;
        }
        return s;
    }
    private:
    vector<int> data;
};

class SlidingWindowProduct {
    public:
    SlidingWindowProduct() {

    }

    void add(int num) {
        data.push_back(num);
    }

    int product(int k) {
        int s = 1;
        for (int i = 0; i < k; ++ i) {
            s *= data[data.size() - i - 1];
            if (s == 0) return s;
        }
        return s;
    }
    private:
    vector<int> data;
};

O(1) Math Algorithm to Compute the Sliding Window Product

We can keep tracking a cummulative product, and compute the last K product by the division. However, we have to take care of the zero – which we can just erase the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class SlidingWindowProduct {
    public:
    SlidingWindowProduct() {
 
    }
 
    void add(int num) {
        if (num == 0) {
            data.clear();
        }
        data.push_back(num * s);
        if (num == 0) {
            s = 1;
        } else {
            s = data.back();
        }
    }
 
    int product(int k) {
        if (k >= data.size()) {
            if (data[0] == 0) return 0;
            return data.back();
        }
        int prev = data[static_cast<int>(data.size()) - k - 1];
        if (prev == 0) return data.back();
        return data.back() / prev;
    }
    private:
    vector<int> data;
    int s = 1;
};

class SlidingWindowProduct {
    public:
    SlidingWindowProduct() {

    }

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

    int product(int k) {
        if (k >= data.size()) {
            if (data[0] == 0) return 0;
            return data.back();
        }
        int prev = data[static_cast<int>(data.size()) - k - 1];
        if (prev == 0) return data.back();
        return data.back() / prev;
    }
    private:
    vector<int> data;
    int s = 1;
};

The time complexity is O(1) constant, and the space complexity is O(N) – as we are using a vector to store the cummulative product.

–EOF (The Ultimate Computing & Technology Blog) —