Successful Pairs of Spells and Potions
Medium · Binary Search · Array · Two Pointers · Binary Search · Sorting
Problem
You have n spells and m potions, given as their strengths spells and potions. A spell of strength s and a potion of strength p make a successful pair when s * p >= success.
Return an array pairs of length n where pairs[i] is the number of potions that make a successful pair with spell i.
The products can reach 10^10, past the range of a 32-bit integer.
Examples
Input: spells = [5, 1, 3], potions = [1, 2, 3, 4, 5], success = 7 Output: [4, 0, 3]
Spell 5 needs a potion of at least 2: four of them. Spell 1 would need 7: none. Spell 3 needs at least 3: three.
Input: spells = [3, 1, 2], potions = [8, 5, 8], success = 16 Output: [2, 0, 2]
Spell 3 needs at least 6 (the two 8s), spell 1 needs 16, spell 2 needs 8.
Input: spells = [10, 100000], potions = [100000, 50000], success = 10000000000 Output: [0, 1]
Only 100000 × 100000 reaches 10^10.
Constraints
- 1 <= n, m <= 10^5
- 1 <= spells[i], potions[j] <= 10^5
- 1 <= success <= 10^10
Approaches
- Count every pair — time O(n · m), space O(n)
Follow-up
If spells arrive one at a time, the binary search answers each in O(log m) after one sort. Asking for the total over all spells, or for the weakest working potion instead of a count, are the two use cases.
Related problems
Start free on Cariara · Coding problems · System design studio
