TL;DR
Sort potions, binary search the success cutoff per spell — O((n + m) log m) time, O(1) extra space (O(n) output).
Approach 1 — Brute force
Try every spell against every potion.
from typing import List
def successfulPairs(spells: List[int], potions: List[int], success: int) -> List[int]:
pairs: List[int] = []
for s in spells:
count = 0
for p in potions:
if s * p >= success:
count += 1
pairs.append(count)
return pairs
- Time: O(n·m). Space: O(1) beyond the output.
With n = m = 10^5 that is up to 10^10 multiplications, far too slow. The constraints rule this out.
Approach 2 — Sort potions + binary search per spell
For a spell of strength s, potion p succeeds iff p >= success / s. This is a threshold condition: once the potions are sorted, the successes form a suffix, so the count is m - (index of first success), which binary search finds directly.
Binary search is the classical O(log m) method of locating a boundary in a sorted array by halving the interval each step; bisect_left(a, x) returns the first index whose value is >= x.
To avoid floating-point error on values up to 10^10, use integer ceiling division: the smallest integer potion that works is need = (success + s - 1) // s.
import bisect
from typing import List
def successfulPairs(spells: List[int], potions: List[int], success: int) -> List[int]:
potions.sort()
m = len(potions)
pairs: List[int] = []
for s in spells:
need = (success + s - 1) // s # ceil(success / s), all-integer
first = bisect.bisect_left(potions, need)
pairs.append(m - first)
return pairs
Walkthrough on spells = [5,1,3], potions = [1,2,3,4,5], success = 7 (potions already sorted, m = 5):
| spell s | need = ceil(7/s) | bisect_left → first | count = 5 − first |
|---|
| 5 | 2 | 1 | 4 |
| 1 | 7 | 5 | 0 |
| 3 | 3 | 2 | 3 |
Result [4, 0, 3] — matches the expected output.
- Time: O(m log m) to sort + O(n log m) for the searches = O((n + m) log m).
- Space: O(1) beyond the output (sort is in place).
Approach 3 — Sort both + two pointers
If you process spells from strongest to weakest, the cutoff need only increases, so the boundary pointer into the sorted potions only moves rightward: one total sweep instead of n independent searches. This is the two-pointer sweep alternative to repeated binary search.
from typing import List
def successfulPairs(spells: List[int], potions: List[int], success: int) -> List[int]:
potions.sort()
m = len(potions)
order = sorted(range(len(spells)), key=lambda i: -spells[i])
pairs = [0] * len(spells)
j = 0 # potions[0..j-1] fail for the current (and all weaker) spells
for i in order:
s = spells[i]
while j < m and s * potions[j] < success:
j += 1
pairs[i] = m - j
return pairs
Walkthrough on the same example — spells in descending order are 5, 3, 1:
s = 5: advance j past potion 1 (5·1 = 5 < 7) → j = 1, count 5 - 1 = 4 at index 0.s = 3: advance past potion 2 (3·2 = 6 < 7) → j = 2, count 3 at index 2.s = 1: advance past 3, 4, 5 (all products < 7) → j = 5, count 0 at index 1.
Result [4, 0, 3].
- Time: O(n log n + m log m) for the sorts; the sweep itself is O(n + m).
- Space: O(n) for the index ordering.
Same asymptotics once sorting dominates. The bisect version is simpler and is the canonical answer; the two-pointer version helps when the predicate is expensive to evaluate repeatedly.
Common pitfalls
- Computing the cutoff as
success / s in floating point — at success = 10^10 a float can round the boundary the wrong way. Use (success + s - 1) // s or compare products directly.
- Using
bisect_right instead of bisect_left: pairs meeting the threshold exactly (p == need with s * p == success) must count as successes.
- Forgetting that the output must follow the original spell order — if you sort spells, carry their indices along.
- Sorting
spells instead of potions in the bisect version: the array you binary search must be the sorted one.
Pattern takeaway
When a condition has the shape “value ≥ threshold” against a fixed collection, sort the collection once and every query becomes a binary search for the boundary; the answer is a suffix (or prefix) length. And when the queries themselves can be ordered so the threshold moves monotonically, the n binary searches collapse into one two-pointer sweep.