⚡Flashcard Drill➔
NeetCode #274LC-2300MediumBinary Search
← Back to All Problems

#274 · #2300 · Successful Pairs of Spells and Potions(咒语和药水的成功对数)

📌 Problem Statement & Constraints

You are given two positive integer arrays spells and potions, and an integer success. A spell and a potion form a successful pair if their product is at least success. Return an array where pairs[i] is the number of potions that form a successful pair with spells[i]. Constraints: 1 <= n, m <= 10^5, 1 <= spells[i], potions[i] <= 10^5, 1 <= success <= 10^10.

💡 Core Algorithmic Approaches

  1. Sort potions. For each spell, the required minimum potion strength is ceil(success / spell).
  2. Then a binary search (bisect_left) finds the first potion at least that strong, and the count is m - index.
  3. This is O((n + m) log m), far better than the O(n * m) brute force.
  4. Computing the required strength with integer arithmetic avoids floating-point issues.

💻 Benchmark Python3 Implementation

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        from bisect import bisect_left
        potions.sort()
        m = len(potions)
        res = []
        for s in spells:
            need = (success + s - 1) // s     # ceiling of success / s
            idx = bisect_left(potions, need)  # first potion strong enough
            res.append(m - idx)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m log m + n log m): sorting the potions plus a binary search per spell.
💾 Space Complexity
O(1) beyond the output (the sort is in place).

⚠️ Interview Pitfalls & Follow-ups

  • Using success / s and math.ceil: floating-point precision breaks for values near 10^10; the integer ceiling (success + s - 1) // s is exact.
  • Forgetting to sort the potions: the binary search requires sorted input.
  • Counting the potions below the threshold instead of above: the answer is m - idx.
  • Nested loops: O(n * m) = 10^10 operations, which times out.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems