Prefix/Postfix sum C++ | 99% Faster in time
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem asks us to find out the number of potion values that has product with a spe
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem asks us to find out the number of potion values that has product with a specific spell value which is greater than (or equal to) a threshold.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSince we have to find the amount of values that is greater than a value, the easiest way is to sort the whole array, then do binary search to find out the position that has the smallest element that satisfy the problem. However, since this approach takes `O(nlogn)` times, which might not be the best idea (in my opinion), for the input with size of 10^5, so I got another idea.\n\nMy idea was, couting occurences of all numbers, then add from the end, using postfix sum, so that, `postfix[n]` is the number of numbers that has value greater than or equal to value `n` in `potions`. Then, that would take `O(1)`, instead of `O(log n)` for each time do searching for each spell, and `O(n)` for counting, instead of `O(nlogn)` do sorting.\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {\n        int postfix[100001] = {0};\n        for(auto potion: potions) postfix[potion]++;\n        for(int i=99999; i>=0; --i) postfix[i] += postfix[i+1];\n\n        //No need extra space at all for storing final result\n        for(int i=0; i<spells.size(); ++i){\n            long long val = success / (long long) spells[i];\n            if(success % (long long) spells[i] != 0) val++;\n\n            spells[i] = val <= 1e5 ? postfix[val] : 0;\n        }\n        return spells;\n    }\n};\n```
['C++']