Successful Pairs of Spells and Potions — Sort and Binary Search [LC 2300]

Problem Statement#

LeetCode 2300 — Successful Pairs of Spells and Potions · Difficulty: Medium

You are given two positive integer arrays spells and potions, each of length n and m respectively, and a positive integer success. A pair (spell, potion) is successful if the product spell * potion >= success. Return an integer array pairs of length n where pairs[i] is the number of potions that form a successful pair with the i-th spell.

Constraints:

• n == spells.length
• m == potions.length
• 1 <= n, m <= 10^5
• 1 <= spells[i], potions[i] <= 10^5
• 1 <= success <= 10^10

Example 1:

Input:  spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation: Spell 5: needs potion >= ceil(7/5) = 2. Potions 2,3,4,5 qualify → 4.
             Spell 1: needs potion >= ceil(7/1) = 7. No potion >= 7 → 0.
             Spell 3: needs potion >= ceil(7/3) = 3. Potions 3,4,5 qualify → 3.

Example 2:

Input:  spells = [3,1,2], potions = [8,5,8], success = 16
Output: [2,0,2]
Explanation: Spell 3: needs potion >= ceil(16/3) = 6. Potions 8,8 qualify → 2.
             Spell 1: needs potion >= 16. No potion qualifies → 0.
             Spell 2: needs potion >= 8. Potions 8,8 qualify → 2.

Example 3:

Input:  spells = [10], potions = [1,1,1,1], success = 5
Output: [4]
Explanation: Spell 10: needs potion >= ceil(5/10) = 1. All 4 potions qualify.

Why This Problem Matters#

This problem teaches one of the most important practical binary search patterns: sort once, query many times. The naive approach — for each spell, scan all potions — is O(n * m), which TLEs for n = m = 10^5 (10^10 operations). The optimised approach sorts potions once in O(m log m), then binary searches for each spell in O(log m), giving O((n + m) log m) overall.

This "sort once, binary search per query" pattern appears constantly in real codebases and interviews: range queries, threshold counting, proximity problems. If you can recognise when a brute-force is O(n * m) and apply sorting + binary search to reduce it to O((n + m) log m), you handle a huge class of problems efficiently.

The ceiling division trick — ceil(success / spell) gives the minimum potion value — is also a frequently tested technique that avoids floating-point errors.

The Core Insight#

For a given spell s, we need s * potion >= success, which means potion >= success / s. Since both spell and potion are integers, the minimum valid potion is ceil(success / s).

Why sorting helps: once potions are sorted in ascending order, all potions from index idx onward satisfy potion >= threshold. The count is simply m - idx. We need to find idx — the leftmost index where potions[idx] >= threshold. This is a classic left-boundary binary search.

Ceiling division without floats: ceil(a / b) = (a + b - 1) // b for positive integers. This avoids floating-point precision issues that can cause off-by-one errors.

One sort, n binary searches: sort potions once, then run a binary search for each spell. This reuses the sorted structure efficiently.

Visual Dry Run#

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

Step 1: Sort potions → [1, 2, 3, 4, 5] (already sorted here).

Spell = 5:

• Threshold = ceil(7 / 5) = ceil(1.4) = 2 (or (7 + 5 - 1) // 5 = 11 // 5 = 2)
• Binary search for leftmost index where potions[mid] >= 2

Count = 5 - 1 = 4. Correct.

Spell = 1:

• Threshold = ceil(7 / 1) = 7
• Binary search for leftmost index where potions[mid] >= 7. No such index → lo = 5.
• Count = 5 - 5 = 0. Correct.

Spell = 3:

• Threshold = ceil(7 / 3) = 3 (since (7 + 3 - 1) // 3 = 9 // 3 = 3)
• Binary search finds idx = 2 (potions[2] = 3 >= 3).
• Count = 5 - 2 = 3. Correct.

Common Mistakes#

1. Using floating-point division for threshold — success / spell in Python 3 or JavaScript gives a float. If success = 6, spell = 3, you get 2.0 exactly, which works. But success = 7, spell = 3 gives 2.333.... Using math.ceil(2.333) = 3 is correct, but floating-point precision can fail at edge cases like success = 10^10, spell = 2. Always prefer integer ceiling: (success + spell - 1) // spell.

2. Forgetting to sort potions — sorting spells instead of potions loses the structure needed for binary search. Potions must be sorted because we binary search within them.

3. Sorting spells — sorting spells changes the output order since pairs[i] must correspond to spells[i]. Never sort spells. Sort only potions.

4. Using bisect_right instead of bisect_left — bisect_left finds the leftmost index where potions[idx] >= threshold. bisect_right finds the index after all equal elements, overcounting when potions[idx] == threshold exactly (those should be included).

5. Integer overflow in the product check — spell * potion can reach 10^5 * 10^5 = 10^10, exceeding 32-bit int. Always use 64-bit arithmetic (Python handles this automatically; use long in Java).

6. Off-by-one in count — the answer is m - idx (not m - idx - 1). All potions from index idx to m-1 inclusive qualify. That is m - idx potions.

7. Not handling the edge where no potion qualifies — when lo ends at m after the binary search, m - m = 0. This is correct and handled automatically, but worth verifying your implementation does not crash with an out-of-bounds access.

Solutions#

Python#

import bisect
import math
 
def successfulPairs(spells: list[int], potions: list[int], success: int) -> list[int]:
    potions.sort()               # sort once — O(m log m)
    m = len(potions)
    result = []
 
    for spell in spells:
        # Minimum potion value needed: ceil(success / spell)
        # Integer ceiling: avoids floating-point precision issues
        threshold = (success + spell - 1) // spell
 
        # Find leftmost index where potions[idx] >= threshold
        # bisect_left returns insertion point, which equals first index >= threshold
        idx = bisect.bisect_left(potions, threshold)
 
        # All potions from idx to m-1 qualify
        result.append(m - idx)
 
    return result

JavaScript#

function successfulPairs(spells, potions, success) {
    // Sort potions once — O(m log m)
    potions.sort((a, b) => a - b);
    const m = potions.length;
    const result = [];
 
    for (const spell of spells) {
        // Minimum potion needed: ceil(success / spell)
        // Use BigInt-safe integer ceiling to avoid overflow and float precision issues
        const threshold = Math.ceil(success / spell);
 
        // Left-boundary binary search: find first index where potions[idx] >= threshold
        let lo = 0, hi = m;
        while (lo < hi) {
            const mid = lo + Math.floor((hi - lo) / 2);
            if (potions[mid] >= threshold) {
                hi = mid;        // threshold met: search further left
            } else {
                lo = mid + 1;   // below threshold: first valid index is to the right
            }
        }
 
        // lo is the first qualifying index; m - lo potions qualify
        result.push(m - lo);
    }
 
    return result;
}

Complexity Analysis#

With n = m = 10^5, the brute-force does 10^10 operations. The sort-and-search approach does m log m + n log m ≈ 2 * 10^5 * 17 ≈ 3.4 * 10^6 operations — roughly 3000x faster.

Follow-up Questions#

1. Why not sort spells? — Sorting spells would rearrange pairs[i], breaking the correspondence between spells[i] and pairs[i]. If you need both sorted, keep a mapping of original indices.

2. Can we use two pointers instead of binary search? — Yes, if you sort both arrays. Sort potions ascending, sort spells descending, then walk a pointer across potions for each spell. However, sorting spells loses the index correspondence unless you store and restore it. Binary search avoids this complexity.

3. How to handle success as a large value (up to 10^10) in JavaScript? — JavaScript numbers are 64-bit floats, which can represent integers exactly up to 2^53 (about 9 * 10^15). success <= 10^10 is safely below this. Math.ceil(success / spell) is also safe for these ranges. For truly giant values, use BigInt.

4. What if spells or potions contain 0? — The constraints guarantee spells[i] >= 1 and potions[i] >= 1. If spell were 0, the product would always be 0, and we could short-circuit to 0 pairs without division.

5. How does this relate to the two-sum binary search pattern? — Both use "sort one array, binary search per query." Two-sum's complement search (target - current) is the same structural idea as finding a threshold. The pattern is: reduce a 2D problem to 1D by sorting.

This Pattern Solves#

• LC 2300 — Successful Pairs of Spells and Potions (this problem)
• LC 1855 — Maximum Distance Between a Pair of Values
• LC 2563 — Count the Number of Fair Pairs
• LC 1498 — Number of Subsequences That Satisfy the Given Sum Condition
• LC 981 — Time Based Key-Value Store
• Any problem where each query asks "how many elements in a sorted set satisfy a threshold condition?"

Key Takeaway#

When you need to count "how many elements in array B satisfy a condition relative to each element in array A," the answer is almost always sort B, binary search per element of A. This reduces O(n * m) brute force to O((n + m) log m). For this specific problem: for each spell, compute the minimum potion threshold using integer ceiling division, then use left-boundary binary search to find the first qualifying potion. The count is m - leftmost_qualifying_index.

Key Takeaways#

• LC 2300 combines sorting with per-query binary search — asked in Google and Amazon assessments to test the "sort once, query many times" optimisation pattern.
• For each spell s, the minimum potion p that forms a successful pair satisfies s * p >= success, so p >= ceil(success / s).
• Sort potions once in O(m log m), then for each spell use left-boundary binary search to find the first qualifying potion index in O(log m).
• The count of successful pairs for spell s is m - leftBoundaryIndex — elements from the boundary to the end all qualify.
• Integer ceiling division avoids floating-point: ceil(success / s) equals (success + s - 1) // s in integer arithmetic.
• Do NOT sort spells — sorting them would break the index correspondence between spells[i] and pairs[i].
• This pattern generalises to any problem asking "for each element in A, how many elements in B satisfy a threshold condition?" — sort B, binary search per A element.