NeetCode #274LC-2300MediumBinary Search
← Back to All Problems#274 · #2300 · Successful Pairs of Spells and Potions(咒语和药水的成功对数)
📌 Problem Statement & Constraints
You are given two positive integer arrays
spells and potions, and an integer success. A spell and a potion form a successful pair if their product is at least success. Return an array where pairs[i] is the number of potions that form a successful pair with spells[i]. Constraints: 1 <= n, m <= 10^5, 1 <= spells[i], potions[i] <= 10^5, 1 <= success <= 10^10.💡 Core Algorithmic Approaches
- Sort
potions. For each spell, the required minimum potion strength isceil(success / spell). - Then a binary search (
bisect_left) finds the first potion at least that strong, and the count ism - index. - This is O((n + m) log m), far better than the O(n * m) brute force.
- Computing the required strength with integer arithmetic avoids floating-point issues.
💻 Benchmark Python3 Implementation
class Solution:
def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
from bisect import bisect_left
potions.sort()
m = len(potions)
res = []
for s in spells:
need = (success + s - 1) // s # ceiling of success / s
idx = bisect_left(potions, need) # first potion strong enough
res.append(m - idx)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m log m + n log m): sorting the potions plus a binary search per spell.
💾 Space Complexity
O(1) beyond the output (the sort is in place).
⚠️ Interview Pitfalls & Follow-ups
- Using
success / sandmath.ceil: floating-point precision breaks for values near 10^10; the integer ceiling(success + s - 1) // sis exact. - Forgetting to sort the potions: the binary search requires sorted input.
- Counting the potions below the threshold instead of above: the answer is
m - idx. - Nested loops: O(n * m) = 10^10 operations, which times out.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.