Successful Pairs of Spells and Potions: Binary Search on Sorted Array

Successful Pairs of Spells and Potions is LeetCode 2300. A spell and potion pair is "successful" if their product is at least success. The brute force way is to check every spell against every potion, but that is too slow for the given constraints. The key insight: sort the potions array once, then binary search for each spell to find where the threshold lies. Everything to the right of the threshold is a successful pair.

The problem

You are given two arrays, spells and potions, along with a long integer success. A pair (i, j) is successful if spells[i] * potions[j] >= success. For each spell, return the number of potions that form a successful pair with it.

Example: spells = [5, 1, 3], potions = [1, 2, 3, 4, 5], success = 7. Output: [4, 0, 3].

Why sorting enables binary search

The brute force approach checks every spell-potion pair, which is O(n * m). That is too slow when both arrays can have up to 10^5 elements.

Here is the observation that changes everything. If you sort the potions array, then for any given spell, the products spell * potion increase as you move right through the sorted potions. That means there is a boundary: every potion to the left of the boundary produces a product below success, and every potion at or to the right of the boundary produces a product at or above success.

Finding that boundary in a sorted array is exactly what binary search does. Instead of checking all n potions for each spell, you binary search in O(log n) time.

The approach

For each spell s, you need a potion p such that s * p >= success. Rearranging, you need p >= success / s. Since potions are integers, you need p >= ceil(success / s). Sort the potions array once, then for each spell, binary search for the leftmost position where potions[idx] >= ceil(success / s). The number of successful potions is len(potions) - idx.

Visual walkthrough

For each spell, the binary search finds the leftmost potion that meets the threshold. Everything from that index to the end of the sorted array is a successful pair. The total work per spell is O(log n), and with m spells that gives O(m log n) for the search phase on top of the O(n log n) sort.

The solution

def successfulPairs(spells, potions, success):
    potions.sort()
    n = len(potions)
    result = []

    for spell in spells:
        min_potion = -(-success // spell)
        lo, hi = 0, n
        while lo < hi:
            mid = (lo + hi) // 2
            if potions[mid] >= min_potion:
                hi = mid
            else:
                lo = mid + 1
        result.append(n - lo)

    return result

Let's break this down piece by piece.

potions.sort() sorts the potions array in ascending order. This is the one-time cost that enables binary search for every spell.

min_potion = -(-success // spell) computes ceil(success / spell) using integer arithmetic. This is the minimum potion value needed for a successful pair with this spell.

lo, hi = 0, n sets up a half-open search range [0, n). Note hi = n, not n - 1, because the answer might be past the end of the array (meaning no potion is large enough).

if potions[mid] >= min_potion: hi = mid keeps the current position as a candidate and searches left for an even earlier valid position. This finds the leftmost valid index.

else: lo = mid + 1 eliminates the left half since those potions are too small.

n - lo is the count of potions from index lo to the end, all of which form successful pairs.

Complexity analysis

The building blocks

Sort then binary search

When you need to count elements satisfying a threshold condition, sort the array and binary search for the boundary. Everything on one side of the boundary satisfies the condition. This reduces per-query time from O(n) to O(log n).

The pattern shows up frequently. In this problem, you sort potions and find the minimum potion that makes a product large enough. In Two Sum II, you work with a sorted array and use two pointers. In Koko Eating Bananas, you binary search over the answer space rather than a data array, but the search mechanics are the same. Any time you see a threshold condition over sorted data, think binary search.

Edge cases

• Spell value is 0. No product can reach a positive success. Result is 0 for that spell. (Problem constraints may guarantee spell is at least 1.)
• All potions succeed. When even the smallest potion times the spell is at least success. Binary search returns index 0, count = n.
• No potions succeed. When even the largest potion times the spell is less than success. Binary search returns index n, count = 0.
• success is 1. Every non-zero spell-potion pair succeeds, so the answer is n for every spell.
• Large values. success can be up to 10^10. Use integer ceiling division to avoid float precision issues.

From understanding to recall

This problem combines two fundamental skills: sorting and binary search. The core logic is clean. Sort the potions, compute the minimum potion threshold with ceiling division, and binary search for the leftmost position meeting that threshold.

The tricky part is getting the details right under pressure. Is hi initialized to n or n - 1? Do you use hi = mid or hi = mid - 1? What is the ceiling division formula again? These small decisions are easy to second-guess during an interview. Spaced repetition drills them into muscle memory so you can write the solution without hesitation and spend your time on problems that actually require creative thinking.

Related posts

• Binary Search - The fundamental binary search template used here
• Koko Eating Bananas - Another problem combining binary search with a threshold condition
• Search Insert Position - Finding the leftmost insertion point in a sorted array