Successful Pairs of Spells and Potions

Solving tips

For a fixed spell s, potion p succeeds iff p >= success/s; sort potions once so the successes form a suffix and each spell's count is m minus the boundary index.
Per spell, binary search (bisect_left) for the first potion >= the cutoff; compute the cutoff with integer ceiling division need = (success + s - 1)//s to avoid float rounding at values up to 1e10.
Target O((n+m) log m) time; use bisect_left (not bisect_right) so pairs meeting the threshold exactly still count.
Alternative: sort both and sweep spells strongest-to-weakest with a monotonic two-pointer, collapsing the n searches into one pass (carry original indices for output order).

Problem

You have an array spells of spell strengths and an array potions of potion strengths. A spell–potion pair is successful when the product of their strengths is at least a given threshold success.

For each spell, count how many potions form a successful pair with it. Return the counts as an array pairs where pairs[i] corresponds to spells[i].

Examples

spells = [5,1,3], potions = [1,2,3,4,5], success = 7 → [4,0,3] Spell 5 pairs with potions 2,3,4,5 (products 10,15,20,25); spell 1 reaches at most 5; spell 3 pairs with 3,4,5 (products 9,12,15).
spells = [3,1,2], potions = [8,5,8], success = 16 → [2,0,2] Spell 3: products 24,15,24 → two successes; spell 1 maxes at 8; spell 2: 16,10,16 → two successes.
spells = [10], potions = [1,1,1], success = 100 → [0] Every product is 10, below the threshold.

Constraints

1 <= len(spells), len(potions) <= 10^5
1 <= spells[i], potions[j] <= 10^5
1 <= success <= 10^10
The sizes rule out checking all n * m pairs (up to 10^10 products).

Think about it first

Hint 1

For a fixed spell of strength `s`, which potions succeed? Is there a single cutoff value that separates failures from successes?

Hint 2

A potion `p` succeeds with spell `s` exactly when `p >= success / s`. If the potions are sorted, all successful potions form a suffix of the array.

Hint 3

Sort `potions` once. For each spell, binary search for the first potion `>= ceil(success / s)` — or use `bisect_left` with the exact fraction — and the answer is `m` minus that index. Watch out for floating-point: prefer integer ceiling division `(success + s - 1) // s`.

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


class Solution:
    def successfulPairs(self, 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 10^10 multiplications — hours of work. The constraints exist precisely to kill this.

Approach 2 — Sort potions + binary search per spell

The insight: for a spell of strength s, potion p succeeds iff p >= success / s. That is a threshold condition — once the potions are sorted, the successes are exactly a suffix, so the count is m - (index of first success), findable by binary search.

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


class Solution:
    def successfulPairs(self, 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

The insight: 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 classic two-pointer/monotonic-sweep alternative to repeated binary search.

from typing import List


class Solution:
    def successfulPairs(self, 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, while the two-pointer version shines when you’d otherwise binary search with an expensive predicate.

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.