🔥 C++ Beginner Friendly Explanation - Brute Force to Optimized Intuition 🤔
Brute Force [Time Limit Exceeded]\n\n## Intuition\nInitially, it sounds like we can just multiply each spell for each potion, but this is not fast enough.\n\n##
# Brute Force [Time Limit Exceeded]\n\n## Intuition\nInitially, it sounds like we can just multiply each `spell` for each `potion`, but this is not fast enough.\n\n## Algorithm Design\n- Loop for each `spell`\n   - Loop for each `potion`\n       - Increase count if the product is $$>=$$ `success`\n\n## Code\n```cpp\nclass Solution {\npublic:\n    // T:O(n*m), S:O(1)\n    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {\n        vector<int> numPairs(spells.size(), 0);\n\n        // Loop through all spells\n        for(int i = 0; i < spells.size(); i++) { // O(n)\n            int spell = spells[i];\n            int count = 0;\n\n            // Loop through all potions for each spell\n            for(int potion: potions) { // O(m)\n\n                // Increment count if it exceeds success\n                long long pair = (long long)potion * (long long)spell;\n                if(pair >= success) count++;\n            }\n            numPairs[i] = count;\n        }\n\n        return numPairs;\n    }\n};\n```\n\n## Complexity\nLet\'s define `m` as the length of `spells` and `n` as the length of `potions`.\n\n- Time Complexity: $$O(n*m)$$\n- Space Complexity: $$O(1)$$\n  - The resulting array is not considered as space.\n\n# Binary Search [Accepted]\n\n## Intuition\nTo reduce search time, we can almost always use binary search. However, the prequisite is sorting. Here, we only need to sort `potions` and find the minimum potion needed to be $$>=$$ `success`.\n\n## Algorithm Design\n- Sort potions\n- Loop for each `spell`\n    - Find index of the minimum potion needed\n    - Calculate the distance since every greater idx is $$>=$$ `success`\n\n## Code\n```cpp\nclass Solution {\npublic:\n    // T:O(m log m + n log m), S:O(log m)\n    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {\n        vector<int> numPairs(spells.size(), 0);\n\n        // Sort potions\n        sort(potions.begin(), potions.end()); // O(m log m)\n\n        // Loop through all spells\n        for(int i = 0; i < spells.size(); i++) { // O(n)\n            // Find the minimum potion needed for success\n            long long potionNeeded = ceil(static_cast<double>(success) / spells[i]);\n\n            // Find the smallest idx position\n            auto it = lower_bound(potions.begin(), potions.end(), potionNeeded); // O(log m)\n            int idx = it - potions.begin();\n\n            // Calculate count based on the index\n            int numPair = potions.size() - (it - potions.begin());\n            numPairs[i] = max(0, numPair);\n        }\n\n        return numPairs;\n    }\n};\n```\n\n## Complexity\nLet\'s define `m` as the length of `spells` and `n` as the length of `potions`.\n\n- Time Complexity: $$O((m + n)log m)$$\n- Space Complexity: $$O(log m)$$\n    - Sorting in C++ takes $$O(log m)$$ space.\n    - The resulting array is not considered as space.\n    \n# Two Pointers [Accepted]\n\n## Intuition\nSince a larger number will always be able to form products $$>=$$ `success` compared to a smaller number, we can use a greedy two pointer approach. \n\n#### For example:\nspells: [1,2,3]\npotions: [1,2]\nsuccess: 4\n\nIf we take the leftmost `spell` (1) and multiply with rightmost `potion` (2), we get a product of 2. This means any potion of a smaller index will not be possible. If we are able to form a product $$>=$$ `success`, that means any greater `spell` number can form it too.\n\n## Algorithm Design\n- Remember the index of `spells` since we will be sorting\n- Sort `potions` and `spells`\n- Initialize two pointers:\n    - Leftmost of `spells`\n    - Rightmost of `potions`\n- While we can form product $$>=$$ `success`, we should decrement `potion` pointer. \n\n## Code\n```cpp\nclass Solution {\npublic:\n    // T:O(n log n + m log m), S:O(n + log m)\n    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {\n        unordered_map<int, pair<int, int>> pairsMap; // {spells[i], {idx, numPair}}\n\n        // Copy spells into numPairs\n        vector<int> numPairs(spells); // O(n)\n        \n        // Add each number into the map\n        for(int i = 0; i < spells.size(); i++) { // O(n)\n            pairsMap[spells[i]] = {i, -1};\n        }\n\n        // Sort both spells and potion\n        sort(spells.begin(), spells.end()); // O(n log n)\n        sort(potions.begin(), potions.end()); // O(m log m)\n\n        // Two pointer approach\n        // Spell pointer starts from the left\n        // Potion pointer starts from the right\n        int potionPtr = potions.size() - 1;\n        for(int i = 0; i < spells.size(); i++) { // O(m)\n            int spell = spells[i];\n            while(potionPtr >= 0 && (long long) spell * potions[potionPtr] >= success) {\n                potionPtr--;\n            }\n            pairsMap[spell] = {pairsMap[spell].first, potions.size() - 1 - potionPtr};\n        }\n\n        // Put data into vector\n        int idx = 0;\n        for(int spell: numPairs) { // O(n)\n            numPairs[idx++] = pairsMap[spell].second;\n        }\n\n        return numPairs;\n    }\n};\n```\n\n## Complexity\nLet\'s define `m` as the length of `spells` and `n` as the length of `potions`.\n\n- Time Complexity: $$O(n log n + m log m)$$\n- Space Complexity: $$O(n + log m)$$\n    - Sorting in C++ takes $$O(log n)$$ space.\n    - The resulting array is not considered as space.
['Two Pointers', 'Binary Search', 'Sorting', 'C++']