Problem Overview
LeetCode 2300 — Successful Pairs of Spells and Potions — gives you two arrays: spells[] and potions[], plus a long integer success. For each spell, you must count how many potions form a successful pair, where a pair is successful if spell * potion >= success. The result is an integer array of the same length as spells, where result[i] is the count of successful potions for spells[i].
For example, spells = [5, 1, 3], potions = [1, 2, 3, 4, 5], success = 7. For spell 5: 5*1=5 (no), 5*2=10 (yes), 5*3=15 (yes), 5*4=20 (yes), 5*5=25 (yes) → 4 pairs. For spell 1: only 1*7 would pass but max potion is 5, so 1*5=5 < 7 → 0 pairs. For spell 3: 3*3=9 >= 7 (yes), 3*4=12 (yes), 3*5=15 (yes) → 3 pairs. Result: [4, 0, 3].
This is a Medium-rated problem that combines two classic techniques: sorting and binary search. The naive approach of checking every (spell, potion) pair is O(n*m) which is too slow. The insight is that once potions are sorted, for each spell there is a clear threshold — any potion at or above the threshold works, and they form a contiguous suffix of the sorted array.
- 1 <= spells.length, potions.length <= 10^5
- 1 <= spells[i], potions[j] <= 10^5
- 1 <= success <= 10^10
- Return result array of length equal to spells.length
- A pair (spells[i], potions[j]) is successful if spell * potion >= success
Brute Force Approach
The brute-force solution uses two nested loops: for each spell, iterate through every potion and check if spell * potion >= success. If it does, increment a counter. After checking all potions for a spell, record the counter in the result array. This is straightforward and correct.
The time complexity of brute force is O(n*m) where n is the length of spells and m is the length of potions. With both arrays up to 10^5 elements, this means up to 10^10 operations — far too slow for LeetCode's time limits. The space complexity is O(1) extra beyond the output array.
The key observation for optimization is that for any fixed spell, the product spell * potion is monotonically increasing as potion increases. If potions were sorted, we could binary search for the exact boundary where the product first meets or exceeds success, rather than checking every element.
Sort Once, Search Per Spell
Sort the potions array once in O(m log m), then binary search for each spell in O(log m). Total time drops from O(n*m) to O((n+m) * log m) — a massive improvement. With n=m=10^5, brute force does 10^10 operations while sort-and-search does roughly 10^5 * 17 ≈ 1.7 million operations.
Sort Potions
The first step of the optimized solution is to sort the potions array in ascending order. This O(m log m) preprocessing step is done once and enables efficient binary search for every spell. After sorting, the potions array forms a monotonically non-decreasing sequence.
Once sorted, for a given spell value, the valid potions (those satisfying spell * potion >= success) form a contiguous suffix of the array. The invalid potions (too small) form a prefix. The boundary between the prefix and suffix is the exact index we need to find via binary search.
The count of valid potions for a given spell equals the number of elements in the suffix — that is, len(potions) minus the index of the first valid potion. If that index is 0, all potions are valid. If that index equals len(potions), no potion is valid.
- 1Sort potions[] in ascending order: O(m log m) one-time cost
- 2For each spell in spells[], compute the minimum potion needed
- 3min_potion = ceil(success / spell) — the smallest potion that passes the threshold
- 4Use binary search to find the leftmost index where potions[index] >= min_potion
- 5Count of valid potions = len(potions) - found_index
Binary Search for Threshold
For each spell, compute the minimum potion value that satisfies spell * potion >= success. Rearranging: potion >= success / spell. Since potion must be an integer and we need strict satisfaction, we take the ceiling: min_potion = ceil(success / spell). Any potion >= min_potion in the sorted potions array forms a valid pair.
Binary search on the sorted potions array finds the leftmost index where potions[index] >= min_potion. In Python this is bisect_left(potions, min_potion). In Java, Arrays.binarySearch returns either the exact index or a negative insertion-point encoding. The count of valid potions is simply len(potions) - leftmost_index.
The binary search runs in O(log m) per spell. With n spells total, the search phase is O(n log m). Combined with the O(m log m) sort, total time is O((n+m) log m). Space is O(m) for sorting in-place (or O(1) if you sort in-place and the language permits mutating the input).
bisect_left in Python, Arrays.binarySearch in Java
Python's bisect module provides bisect_left(potions, min_potion) which directly returns the leftmost index where min_potion could be inserted — exactly the first index >= min_potion. In Java, use Arrays.binarySearch and decode negative returns: if result < 0, the insertion point is (-result - 1). Both give O(log m) per spell with no manual binary search implementation needed.
Ceiling Division Trick
Computing ceil(success / spell) requires care to avoid floating-point errors. With success up to 10^10 and spell up to 10^5, floating-point division can lose precision for large inputs. The safe integer formula is: min_potion = (success + spell - 1) // spell. This is equivalent to ceiling division in integer arithmetic.
Why does this work? For any integers a and b where b > 0, ceil(a/b) = (a + b - 1) // b. When a is exactly divisible by b, (a + b - 1) // b = a//b + (b-1)//b = a//b + 0 = a//b = ceil(a/b). When a is not exactly divisible, the (b-1) term bumps the result up by exactly 1, giving the ceiling. No floating-point involved.
This ceiling division trick is critical for correctness with large numbers in LeetCode 2300. Using float division like math.ceil(success / spell) can fail on edge cases near 10^15 due to IEEE 754 double precision limits (about 15-16 significant digits). Always prefer the integer formula in competitive programming.
- 1Goal: find the minimum integer potion such that spell * potion >= success
- 2Rearrange: potion >= success / spell (real division)
- 3Take ceiling since potion must be an integer: potion >= ceil(success / spell)
- 4Integer formula: min_potion = (success + spell - 1) // spell
- 5This avoids float and is exact for all values within the constraint range
Code Walkthrough — Python and Java
Python solution using bisect: import bisect; def successfulPairs(spells, potions, success): potions.sort(); m = len(potions); return [m - bisect.bisect_left(potions, (success + s - 1) // s) for s in spells]. The list comprehension runs one binary search per spell. Time O((n+m) log m), space O(m) for in-place sort or O(1) extra if mutation is allowed.
Java solution: Arrays.sort(potions); int[] result = new int[spells.length]; for (int i = 0; i < spells.length; i++) { long minPotion = (success + spells[i] - 1) / spells[i]; int idx = Arrays.binarySearch(potions, (int)minPotion); if (idx < 0) idx = -idx - 1; else while (idx > 0 && potions[idx-1] >= minPotion) idx--; result[i] = potions.length - idx; }. Note the edge-case handling for duplicate values in binarySearch.
Both solutions achieve the same asymptotic complexity. The Python bisect_left is cleaner because it always returns the leftmost insertion point without needing duplicate handling. The Java Arrays.binarySearch can land on any occurrence of the target value in case of duplicates, requiring a leftward scan — or use a manual binary search that always seeks the leftmost position.
Use Ceiling Division, Not Floor
Using floor(success / spell) instead of ceil(success / spell) will undercount pairs. Example: success=7, spell=3 → ceil(7/3)=3. Potion 3 gives 3*3=9 >= 7 (valid). But floor(7/3)=2 → you would search for potions >= 2, which includes potions that are too small when multiplied. Always compute min_potion = (success + spell - 1) // spell, not success // spell.