663. Successful Pairs of Spells and Potions
You are given two arrays of positive integers, spells (length n) and potions (length m), together with an integer success. spells[i] is the strength of the i-th spell and potions[j] is the strength of the j-th potion.
Mixing spell i with potion j is successful when the product spells[i] * potions[j] is at least success.
Return an array pairs of length n where pairs[i] is the number of potions that make a successful mix with the i-th spell.
Notice that products can reach 10^10 — watch your integer widths.
Example 1:
Input: spells = [5, 1, 3], potions = [1, 2, 3, 4, 5], success = 7
Output: [4, 0, 3]
Explanation: Spell 5 pairs with potions 2,3,4,5 (products 10,15,20,25 ≥ 7) → 4. Spell 1 reaches at most 5, never 7 → 0. Spell 3 pairs with potions 3,4,5 (products 9,12,15) → 3.
Example 2:
Input: spells = [3, 1, 2], potions = [8, 5, 8], success = 16
Output: [2, 0, 2]
Explanation: Spell 3 gives products 24, 15, 24 — two of them reach 16. Spell 1 tops out at 8. Spell 2 gives 16, 10, 16 — two reach 16 exactly.
Constraints:
- 1 ≤ n, m ≤ 10⁵
- 1 ≤ spells[i], potions[j] ≤ 10⁵
- 1 ≤ success ≤ 10¹⁰
Hints:
For one spell of strength s, checking every potion works but costs O(m) per spell — O(n·m) total, too slow at 10^5 each.
If the potions were sorted, all the potions strong enough for a given spell would sit in one contiguous suffix. How do you find where that suffix starts?
A potion p works for spell s exactly when p >= ceil(success / s). Sort the potions once, then binary-search that threshold for each spell; the answer is m minus the found position.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: spells = [5, 1, 3], potions = [1, 2, 3, 4, 5], success = 7
Expected output: [4, 0, 3]