Skip to content

← leetcode

Successful Pairs of Spells and Potions

· Medium

LeetCode problem 2300

Simply, sort potions from smallest to largest.

sort(potions.begin(), potions.end());

Then, simply iterate through spells, dividing success with newSuccess and binary searching where success / newSuccess should go inside of potions. This allows you to calculate the number of successfulPairs in log(n) time.

for (int& i : spells) {
    long long newSuccess = success / i - (success % i == 0 ? 1 : 0);
    auto it = upper_bound(potions.begin(), potions.end(), newSuccess);
    ans.push_back(potions.end() - it);
}

code

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        sort(potions.begin(), potions.end());
        vector<int> ans;

        for (int& i : spells) {
            long long newSuccess = success / i - (success % i == 0 ? 1 : 0);
            auto it = upper_bound(potions.begin(), potions.end(), newSuccess);
            ans.push_back(potions.end() - it);
        }

        return ans;
    }
};

complexity

  • Time: O(n log(m) + n log(n)) where m denotes the number of elements inside of spells and n denotes the number of elements inside of potions
  • Space: O(n)

time taken

  • 9 minutes and 12 seconds