Successful Pairs of Spells and Potions

Problem in plain words

You have an array of spell strengths and an array of potion strengths, plus a number success. A spell and a potion form a successful pair when the product of their strengths is at least success. For every spell, report how many potions it pairs successfully with.

Example: spells = [2, 6], potions = [4, 1, 3], success = 7. Spell 2 gives products 8, 2, 6, so only one potion works. Spell 6 gives 24, 6, 18, so two work. The answer is [1, 2].

Intuition

For a fixed spell, the product grows as the potion grows. So if the potions are sorted, the successful ones form a suffix: once a potion is strong enough, every potion after it is too. Finding where that suffix starts is a lower-bound binary search. Sort potions once, then each spell costs O(log m).

Approach

1. Sort potions in ascending order.
2. For each spell, binary search for the first index lo with spell × potions[lo] >= success (use 64-bit arithmetic).
3. The count for that spell is m - lo.
4. Collect the counts in spell order and return them.

Dry run

Sorted potions [1, 3, 4], success = 7.

Java solution

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int m = potions.length;
        int[] result = new int[spells.length];
        for (int i = 0; i < spells.length; i++) {
            long spell = spells[i];
            int lo = 0;
            int hi = m; // search in [lo, hi)
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (spell * potions[mid] >= success) {
                    hi = mid;
                } else {
                    lo = mid + 1;
                }
            }
            result[i] = m - lo;
        }
        return result;
    }
}

Python solution

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()
        m = len(potions)
        result = []
        for spell in spells:
            need = (success + spell - 1) // spell  # smallest potion that works
            result.append(m - bisect_left(potions, need))
        return result

Complexity

Edge cases and common mistakes

• Integer overflow — spells and potions go up to 10^5, so the product can be 10^10. Cast to long before multiplying in Java.
• Floating-point division — computing success / spell as a double can round the wrong way. Use integer ceiling division (success + spell - 1) / spell or compare products directly.
• No potion works — the search ends at lo = m, giving a count of 0.
• Sorting spells too — not needed, and it would scramble the output order.