Successful Pairs of Spells and Potions

Problem

Given arrays spells and potions, and an integer success, count how many potions form a successful pair with each spell. A pair is successful if spell * potion >= success.

Approach 1: Binary Search

Sort potions, then for each spell binary search for the minimum potion strength needed.

def solution(spells: list[int], potions: list[int], success: int) -> list[int]:
    potions = sorted(potions)
    n = len(potions)

    results = []
    for s in spells:
        left = 0
        right = len(potions)
        while left < right:
            mid = left + (right - left) // 2
            if potions[mid] >= success / s:
                right = mid
            else:
                left = mid + 1
        results.append(n - left)

    return results

Time Complexity: O(m log m + n log m) where m = len(potions), n = len(spells)

Approach 2: Prefix Sum (Counting)

Instead of sorting and searching, use a counting approach based on the observation that for each potion, we can precompute the minimum spell strength required.

Key Insight

For a potion p to form a successful pair with a spell s:

s * p >= success
s >= success / p
s >= ceil(success / p)

So ceil(success / p) is the minimum spell strength needed to succeed with potion p.

Algorithm

1. For each potion, compute the minimum spell strength needed and count occurrences
2. Build a prefix sum so that sums[s] = count of potions requiring spell strength <= s
3. Look up the answer for each spell directly

def solution(spells: list[int], potions: list[int], success: int) -> list[int]:
    max_spell = max(spells)
    sums = [0] * (max_spell + 1)

    for potion in potions:
        curr = math.ceil(success / potion)
        if curr > max_spell:
            continue
        sums[curr] += 1

    for i in range(1, len(sums)):
        sums[i] = sums[i] + sums[i - 1]

    return [sums[s] for s in spells]

Why Prefix Sum Works

After building sums:

• sums[i] (before prefix sum) = count of potions where minimum required spell is exactly i
• sums[i] (after prefix sum) = count of potions where minimum required spell is <= i

A spell of strength s succeeds with any potion that requires <= s. Therefore sums[s] gives the exact count of successful potions.

Example Trace

spells=[5,1,3], potions=[1,2,3,4,5], success=7

Step 1: For each potion, compute minimum spell needed
- potion=1: ceil(7/1) = 7 > max_spell(5), skip
- potion=2: ceil(7/2) = 4 → sums[4] += 1
- potion=3: ceil(7/3) = 3 → sums[3] += 1
- potion=4: ceil(7/4) = 2 → sums[2] += 1
- potion=5: ceil(7/5) = 2 → sums[2] += 1

sums = [0, 0, 2, 1, 1, 0]  (indices 0-5)

Step 2: Build prefix sum
sums = [0, 0, 2, 3, 4, 4]

Step 3: Look up results
- spell=5: sums[5] = 4
- spell=1: sums[1] = 0
- spell=3: sums[3] = 3

Output: [4, 0, 3]

Time Complexity: O(m + max_spell + n)

Comparison

When max_spell is bounded (constraint: <= 10^5), prefix sum is effectively O(m + n), avoiding the log factor entirely.

The prefix sum approach trades space (array of size max_spell) for time (no log factors). This is a counting/bucket sort style optimization that works when the value range is bounded.