Linear Solution c++
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n1. Find maximum Spell power.\n2. Create an array counts of length max spe
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Find maximum Spell power.\n2. Create an array `counts` of length `max spell power` filled with zeros.\n3. For each potion calculate minimum required spell. If required spell <= maximum spell power, increment counts of required Spell.\n4. Update `counts` , so `counts[i] = sum(counts[0]...counts[i])`. So `counts` now contains total number of "good" potions.\n5. Fill the results, so `results[i] = counts[spells[i]]`. To save some space, we can use spells as results.\n\n# Complexity\n- Time complexity: O(n + m + k)\n    spells.size() = n\n    potions.size() = m\n    max spells power = k\n\n    It can be optimized a little bit. `k` could be `max spells power` - `min spells power`\n\n- Space complexity: O(k)\n  We only use additional space for `counts` array. If we consider `results` as additional space, then O(k+n).\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {\n        int maxSpell = 0;\n        for(int i=0; i<spells.size(); ++i){  //O(n)\n            maxSpell = max(maxSpell, spells[i]);\n        }\n        vector<int> counts(maxSpell+1, 0);\n\n        for(int i=0; i<potions.size(); ++i){ //O(m)\n            auto index = (success+potions[i]-1)/potions[i]; //minimum required spell power\n            if(index<counts.size()) counts[index]++;\n        }\n\n        for(int i=1; i<counts.size(); ++i){ //O(k)\n            counts[i] +=counts[i-1];\n        }\n\n        vector<int> result(spells.size(), 0);\n        for(int i=0; i<spells.size(); ++i){ //O(n)\n            result[i] = counts[spells[i]];\n        }\n        return result;\n    }\n};\n```
['C++']