Successful Pairs of Spells and Potions

How it works

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.

Steps

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.

Complexity

• Time complexity: O(n log n + mlog 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.

Things to watch for

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.

from typing import List

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

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        int n = spells.size(), m = potions.size();
        vector<int> sIdx(n);
        for (int i = 0; i < n; i++) sIdx[i] = i;

        sort(sIdx.begin(), sIdx.end(), [&](int a, int b) {
            return spells[a] < spells[b];
        });

        sort(potions.begin(), potions.end());

        int j = m - 1;
        vector<int> res(n);
        for (int i = 0; i < n; i++) {
            while (j >= 0 && (long long) spells[sIdx[i]] * potions[j] >= success) {
                j--;
            }
            res[sIdx[i]] = m - j - 1;
        }

        return res;
    }
};