Successful Pairs of Spells and Potions — Medium Problem & Solution

A pair of a spell and a potion is successful when the product of their strengths is at least success.

Difficulty: Medium
Topics: Arrays, Sorting, Two Pointers, Binary Search
Asked at: Amazon, Google, Razorpay
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A pair of a spell and a potion is successful when the product of their strengths is at least success.

Return an array whose i-th entry is the number of potions that form a successful pair with spell i.

Example 1

Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation: Spell 5 succeeds with potions 2, 3, 4 and 5.

Example 2

Input: spells = [3,1,2], potions = [8,5,8], success = 16
Output: [2,0,2]

Example 3

Input: spells = [1], potions = [1], success = 1
Output: [1]

Constraints

1 <= spells.length, potions.length <= 100000
1 <= spells[i], potions[j] <= 100000
1 <= success <= 1000000000

How to solve Successful Pairs of Spells and Potions

Sorting the potions turns each spell's question into a lower-bound search: find the first potion whose product with this spell reaches success; everything after it works too.

Approach

Sort potions ascending.
For each spell sp, binary search the first index where sp · potions[mid] >= success.
The count is potions.length - that index.

Why it works

For a fixed positive sp, the product is increasing in the potion's strength, so the successful potions form a suffix of the sorted array and the boundary is unique. Testing with a multiplication avoids the rounding trap of ceil(success / sp), which is easy to get wrong when the division is not exact.

Complexity

Time — O((n + m) log m)
Space — O(m)

Pitfalls

spells[i] · potions[j] reaches 10^5 · 10^5 = 10^10 — the comparison needs 64-bit.
Dividing instead of multiplying needs a ceiling and rounds wrongly at exact multiples.
The answer counts potions, so it is m - index, not the index itself.

Reference solution

Python

from typing import List

def successfulPairs(spells: List[int], potions: List[int], success: int) -> List[int]:
    sorted_potions = sorted(potions)
    n = len(sorted_potions)
    out = []
    for sp in spells:
        lo, hi = 0, n
        while lo < hi:
            mid = (lo + hi) // 2
            if sp * sorted_potions[mid] >= success:
                hi = mid
            else:
                lo = mid + 1
        out.append(n - lo)
    return out

JavaScript

var successfulPairs = function(spells, potions, success) {
    var sorted = potions.slice().sort(function(a, b) { return a - b; });
    var n = sorted.length;
    var out = [];
    for (var i = 0; i < spells.length; i++) {
        var sp = spells[i];
        var lo = 0, hi = n;
        while (lo < hi) {
            var mid = (lo + hi) >> 1;
            if (sp * sorted[mid] >= success) hi = mid; else lo = mid + 1;
        }
        out.push(n - lo);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue