Successful Pairs of Spells and Potions
Successful Pairs of Spells and Potions: for each spell, count how many potions produce a product of at least success when multiplied with it.
- n == spells.length, m == potions.length
- 1 <= n, m <= 10⁵
- 1 <= spells[i], potions[i] <= 10⁵
- 1 <= success <= 10¹⁰
Intuition
Successful pairs of spells and potions counts, for each spell, how many potions produce a product at or above a success threshold. Checking every pair is O(n × m) and too slow at the stated limits.
The structure that saves it is monotonicity. For a fixed spell, the product grows with the potion's strength:
- Sorting the potions means the successful ones form a contiguous suffix, so finding the first successful potion gives the count immediately.
That first index is found by binary search rather than by scanning, turning the inner loop logarithmic.
For a spell of strength s, the smallest successful potion strength is success / s rounded up. Binary searching for that value locates the boundary, and the count is m − index.
The rounding is where implementations break. Integer division truncates, so success / s gives a value that may be too small and admits a potion that actually fails. Using ceiling division — or, more safely, comparing spell × potion >= success directly inside the binary search — avoids the issue entirely.
Comparing products rather than computing a threshold also sidesteps floating-point error, which appears if the division is done in floating point on large values.
Overflow is real: spell × potion can exceed 32-bit range, so 64-bit arithmetic is required in languages where that matters.
Sorting the potions is what matters; the spells are processed in their original order and their results must be returned in that order, so sorting them would need index tracking for no benefit.
Sorting is O(m log m) and each of n spells costs O(log m), giving O(m log m + n log m).
When a per-item condition can be rearranged into 'value ≥ threshold', a sorted array plus binary search answers each query in logarithmic time. The tell is a pairwise condition where one side is constant within the query. Same shape as Two Sum II, Search Insert Position, and any 'count elements at least X' question.
Approach
Before reading on: fix one spell and rearrange the success condition so the potion sits alone on one side. What does that turn each query into, and what must the potions array look like first? Aim for O((n + m) log m).
Spot the monotonicity
For a fixed spell, the product grows with potion strength, so successful potions form a contiguous suffix once the potions are sorted.
Sort the potions only
Spells stay in their original order, since results must be returned that way. Sorting them would require index tracking for no gain.
Binary search the boundary
Find the first potion that succeeds with this spell. The count is then m − index, with no scanning required.
Compare products, not quotients
Test spell * potion >= success inside the search. Computing success / s truncates with integer division and admits a failing potion.
Guard against overflow
spell * potion can exceed 32-bit range, so use 64-bit arithmetic where the language requires it.
Return counts in spell order
Each spell's answer goes at its original index. The potions' sorted order is internal and never affects the output arrangement.
Cost of the approach
Sorting is O(m log m) and each spell costs O(log m), giving O((n + m) log m) time and O(1) extra space beyond the sort.
Solution & live demo
Common pitfalls
Floating-point division for the threshold
threshold = success / spell
threshold = -(-success // spell) # integer ceiling
Values on the exact boundary can round the wrong way, so a potion that should succeed is excluded. Integer ceiling division keeps the comparison exact.
Not sorting the potions
index = bisect_left(potions, threshold) # unsorted
potions.sort() index = bisect_left(potions, threshold)
Binary search assumes order. On an unsorted array it returns an arbitrary position and the counts are silently wrong rather than crashing.
Overflow in the product comparison
int product = spell * potion;
long product = (long) spell * potion;
10⁵ × 10⁵ = 10¹⁰ exceeds a 32-bit int in C++ and Java, wrapping to a negative value and failing the comparison. Python integers are arbitrary precision so this bites only in the ported versions.
Edge cases
The binary search returns m and the count is 0.
The search returns index 0 and the count is m.
Integer ceiling division keeps it inclusive, so that potion counts.
10⁵ × 10⁵ = 10¹⁰ overflows a 32-bit int; use 64-bit arithmetic in C++ and Java.
The search covers a one-element array and returns 0 or 1 correctly.