Skip to content

2300. Successful Pairs of Spells and Potions

Description

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.

 

Example 1:

Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation:
- 0th spell: 5 * [1,2,3,4,5] = [5,10,15,20,25]. 4 pairs are successful.
- 1st spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
- 2nd spell: 3 * [1,2,3,4,5] = [3,6,9,12,15]. 3 pairs are successful.
Thus, [4,0,3] is returned.

Example 2:

Input: spells = [3,1,2], potions = [8,5,8], success = 16
Output: [2,0,2]
Explanation:
- 0th spell: 3 * [8,5,8] = [24,15,24]. 2 pairs are successful.
- 1st spell: 1 * [8,5,8] = [8,5,8]. 0 pairs are successful. 
- 2nd spell: 2 * [8,5,8] = [16,10,16]. 2 pairs are successful. 
Thus, [2,0,2] is returned.

 

Constraints:

  • n == spells.length
  • m == potions.length
  • 1 <= n, m <= 105
  • 1 <= spells[i], potions[i] <= 105
  • 1 <= success <= 1010

Solutions

We can sort the potion array, then traverse the spell array. For each spell \(v\), we use binary search to find the first potion that is greater than or equal to \(\frac{success}{v}\). We mark its index as \(i\). The length of the potion array minus \(i\) is the number of potions that can successfully combine with this spell.

The time complexity is \(O((m + n) \times \log m)\), and the space complexity is \(O(\log n)\). Here, \(m\) and \(n\) are the lengths of the potion array and the spell array, respectively.

1
2
3
4
5
6
7
class Solution:
    def successfulPairs(
        self, spells: List[int], potions: List[int], success: int
    ) -> List[int]:
        potions.sort()
        m = len(potions)
        return [m - bisect_left(potions, success / v) for v in spells]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int n = spells.length, m = potions.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            int left = 0, right = m;
            while (left < right) {
                int mid = (left + right) >> 1;
                if ((long) spells[i] * potions[mid] >= success) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            ans[i] = m - left;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        sort(potions.begin(), potions.end());
        vector<int> ans;
        int m = potions.size();
        for (int& v : spells) {
            int i = lower_bound(potions.begin(), potions.end(), success * 1.0 / v) - potions.begin();
            ans.push_back(m - i);
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
func successfulPairs(spells []int, potions []int, success int64) (ans []int) {
    sort.Ints(potions)
    m := len(potions)
    for _, v := range spells {
        i := sort.Search(m, func(i int) bool { return int64(potions[i]*v) >= success })
        ans = append(ans, m-i)
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function successfulPairs(spells: number[], potions: number[], success: number): number[] {
    potions.sort((a, b) => a - b);
    const m = potions.length;
    const ans: number[] = [];
    for (const v of spells) {
        let left = 0;
        let right = m;
        while (left < right) {
            const mid = (left + right) >> 1;
            if (v * potions[mid] >= success) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        ans.push(m - left);
    }
    return ans;
}

Comments