Java, prefix product, beats 100%, explained
We can easily count the product in O(1) time if we keep the product prefix array - every next element of such array is the product of the previous product and n
We can easily count the product in O(1) time if we keep the product prefix array - every next element of such array is the product of the previous product and next element added to the data structure. \n\nOnly problem with this approach is 0 element - it ruins this logic because every next element after it will be 0 if we just keep multiplying naively. \n\nHowever if you think about it - we don\'t care about element before 0 because all such queries will return 0. The only sequence that can return some value > 0 will be the after the 0. This means that we essentially reset our structure after 0 element and start over.\n\nFor getProduct method we need to check if we have enough elements in our data structure. If not (as per problem statement we should always have enough) it means we have met 0 before and erased the data. In this case we can just return 0. Otherwise return normally as per prefix product logic - arr[N - 1]/arr[N - 1 - k]. \n\nCatches: it\'s easier if we initialize our list with 1 - in this case calculation became easier for cases when we added exactly k elements, otherwise we would need extra logic to check the size(). \nanother cath - we can keep previous element and calculate next element based on it\'s value directly instead of goinmg every time to the list - will save some time\n\nO(1) time for add (on average, if we skip details of dynamic array in java), O(1) getProduct method - few comparisions and one division.\nO(n) space - potentially we can have products of all elements in a list\n\n```\npublic class ProductOfLastKNumbers {\n    List<Integer> list;\n    int prev;\n    public ProductOfLastKNumbers() {\n        list = new ArrayList();\n        list.add(1);\n        prev = 1;\n    }\n\n    public void add(int num) {\n        //if element is > 0 create next element in a prefix product list. Update prev to be this\n        //element\n        if (num > 0) {\n            prev*=num;\n            list.add(prev);\n        }\n        //if this is 0  we need to reinit the structure\n        else {\n            list = new ArrayList();\n            list.add(1);\n            prev = 1;\n        }\n    }\n\n    public int getProduct(int k) {\n        int N = list.size();\n        //in case there are not enough elements by the problem definition it can only happen if\n        //we have met 0 before. In this case return 0. In all other cases we get the product from\n        //division due to prefix product property. Note that list always has n + 1 elements due to \n        //initial 1, we need it to avoid outofbounds checks for edge cases\n        return (k < N) ? prev / list.get(N - 1 - k) : 0;\n    }\n}\n```
['Java']