2300. Successful Pairs of Spells and Potions - Explanation

Problem Link

1. Brute Force

Intuition

For each spell, we need to count how many potions form a successful pair. A pair is successful when spell * potion >= success. The simplest approach is to check every spell against every potion and count the valid combinations.

Algorithm

1. Create a result array res to store the count for each spell.
2. For each spell s in spells:
   • Initialize a counter cnt = 0.
   • For each potion p in potions:
     • If s * p >= success, increment cnt.
   • Append cnt to res.
3. Return res.

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        res = []

        for s in spells:
            cnt = 0
            for p in potions:
                if s * p >= success:
                    cnt += 1
            res.append(cnt)

        return res

Time & Space Complexity

• Time complexity: $O(n * m)$
• Space complexity: $O(1)$

Where $n$ and $m$ are the sizes of the arrays $spells$ and $potions$ respectively.

---

2. Sorting + Binary Search

Intuition

If we sort the potions array, all successful potions for a given spell will be contiguous at the end. For a spell s, we need the minimum potion strength p such that s * p >= success, which means p >= success / s. Binary search can efficiently find this threshold index, and all potions from that index onward form successful pairs.

Algorithm

1. Sort the potions array in ascending order.
2. For each spell s in spells:
   • Use binary search to find the smallest index idx where s * potions[idx] >= success.
   • The count of successful pairs is len(potions) - idx.
   • Store this count in the result.
3. Return the result array.

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()
        res = []

        for s in spells:
            l, r = 0, len(potions) - 1
            idx = len(potions)

            while l <= r:
                m = (l + r) // 2
                if s * potions[m] >= success:
                    r = m - 1
                    idx = m
                else:
                    l = m + 1

            res.append(len(potions) - idx)

        return res

Time & Space Complexity

• Time complexity: $O((m + n) * \log m)$
• Space complexity:
  • $O(1)$ or $O(m)$ extra space depending on the sorting algorithm.
  • $O(n)$ space for the output array.

Where $n$ and $m$ are the sizes of the arrays $spells$ and $potions$ respectively.

---

3. Sorting + Two Pointers

Intuition

If we sort both arrays, we can use the two pointer technique. A weaker spell needs a stronger potion to succeed, and a stronger spell needs at least as weak a potion. By processing spells in ascending order and potions in descending order, we can reuse the potion pointer position. Once a potion works for a spell, it works for all stronger spells too.

Algorithm

1. Save the original spells array and sort both spells and potions.
2. Use a pointer j starting at the end of sorted potions.
3. For each spell in sorted order:
   • Move j left while spell * potions[j] >= success.
   • Store the count m - j - 1 in a map keyed by spell strength.
4. Build the result by looking up each original spell's count in the map.
5. Return the result.

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        n, m = len(spells), len(potions)
        S = spells[:]
        count = defaultdict(int)
        spells.sort()
        potions.sort()

        j = m - 1
        for i in range(n):
            while j >= 0 and spells[i] * potions[j] >= success:
                j -= 1
            count[spells[i]] = m - j - 1

        res = [0] * n
        for i in range(n):
            res[i] = count[S[i]]

        return res

Time & Space Complexity

• Time complexity: $O(n \log n + m\log m)$
• Space complexity:
  • $O(1)$ or $O(m + n)$ extra space depending on the sorting algorithm.
  • $O(n)$ space for the output array.

Where $n$ and $m$ are the sizes of the arrays $spells$ and $potions$ respectively.

---

4. Sorting + Two Pointers (Optimal)

Intuition

The previous approach uses extra space to map spell values to their counts. We can avoid this by sorting indices of spells rather than the spells themselves. This way, we can directly write results to the correct positions in the output array without needing a lookup map.

Algorithm

1. Create an array of indices sIdx and sort it by corresponding spell strength.
2. Sort the potions array.
3. Initialize pointer j at the end of potions and result array res.
4. For each index i in sorted order:
   • Move j left while spells[sIdx[i]] * potions[j] >= success.
   • Set res[sIdx[i]] = m - j - 1.
5. Return res.

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        n, m = len(spells), len(potions)
        sIdx = list(range(n))
        sIdx.sort(key=lambda x: spells[x])
        potions.sort()

        j = m - 1
        res = [0] * n
        for i in range(n):
            while j >= 0 and spells[sIdx[i]] * potions[j] >= success:
                j -= 1
            res[sIdx[i]] = m - j - 1

        return res

Time & Space Complexity

• Time complexity: $O(n \log n + m\log m)$
• Space complexity:
  • $O(1)$ or $O(m + n)$ extra space depending on the sorting algorithm.
  • $O(n)$ space for the output array.

Where $n$ and $m$ are the sizes of the arrays $spells$ and $potions$ respectively.

---

Common Pitfalls

Integer Overflow in Multiplication

When multiplying spell * potion, the result can exceed the range of a 32-bit integer since both values can be up to 10^5, making the product up to 10^10. Always cast to long before multiplication or use a 64-bit integer type to avoid overflow and incorrect comparisons.

Off-by-One Errors in Binary Search

A common mistake is incorrectly calculating the count of successful pairs after binary search. The binary search finds the first index where the condition is satisfied, and the count should be len(potions) - idx. Errors occur when using <= vs < in the binary search condition or when the index represents the wrong boundary.

Forgetting to Sort the Potions Array

Binary search only works on sorted arrays. A frequent oversight is attempting to use binary search on the original unsorted potions array, which leads to incorrect results. The potions array must be sorted first, and for the two-pointer approach, both arrays need to be sorted while preserving the original spell order for the output.