LeetCode 2300 — Successful Pairs of Spells and Potions | Brute Force & Optimal Solution Explained

When you combine the magical powers of spells and potions, you either fail miserably or succeed spectacularly — and in this LeetCode problem, we calculate exactly how many successful combinations exist.

Let’s break down the problem, understand the logic, and implement both brute force and optimal solutions step-by-step.

Problem Link: https://leetcode.com/problems/successful-pairs-of-spells-and-potions/

Problem Description

You are given two positive integer arrays:

• spells[] — strength of each spell
• potions[] — strength of each potion

and an integer success.

A pair (spell, potion) is successful if:

[
spell[i] * potion[j] >= success
]

We need to return an array pairs[], where pairs[i] represents how many potions form a successful pair with the i-th spell.

🧾 Example 1

Input:

spells = [5, 1, 3]
potions = [1, 2, 3, 4, 5]
success = 7

Output:

[4, 0, 3]

Explanation:

• Spell 5: 5 × [1,2,3,4,5] = [5,10,15,20,25] → 4 successful pairs
• Spell 1: 1 × [1,2,3,4,5] = [1,2,3,4,5] → 0 successful pairs
• Spell 3: 3 × [1,2,3,4,5] = [3,6,9,12,15] → 3 successful pairs

Hence, the output is [4, 0, 3].

🧮 Constraints

The constraints make it clear that a brute force O(n × m) approach might be too slow — but we’ll still start with it for understanding.

Brute Force Solution

💭 Idea:

For each spell, check every potion and count how many pairs satisfy spell[i] * potion[j] ≥ success.

🧑‍💻 Code:

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        int n1 = spells.size();
        int n2 = potions.size();
        vector<int> pairs;

        for (int i = 0; i < n1; i++) {
            int count = 0;
            for (int j = 0; j < n2; j++) {
                if (static_cast<long long>(spells[i]) * potions[j] >= success) {
                    count++;
                }
            }
            pairs.push_back(count);
        }
        return pairs;
    }
};

⏱️ Time Complexity:

• O(n × m) → not efficient for large input sizes.

✅ Space Complexity:

• O(1) extra space (excluding output array).

Optimal Solution — Using Sorting + Binary Search

💭 Idea:

1. Sort the potions array.
2. For each spell, find the minimum potion strength required to reach the success threshold.
   [
   potion[j] >= success/spell[i]
   ]
3. Use binary search (lower_bound) to find the first potion that meets this requirement.
4. All potions from that index onward form successful pairs.

🧑‍💻 Code:

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        int n1 = spells.size();
        int n2 = potions.size();
        sort(potions.begin(), potions.end());
        vector<int> pairs;

        for (int i = 0; i < n1; ++i) {
            long long minRequired = (success + spells[i] - 1) / spells[i]; // ceil division
            int idx = lower_bound(potions.begin(), potions.end(), minRequired) - potions.begin();
            pairs.push_back(n2 - idx);
        }

        return pairs;
    }
};

Step-by-Step Example

Input:

spells = [3, 1, 2]
potions = [8, 5, 8]
success = 16

Process:

1. Sort potions → [5, 8, 8]
2. For each spell:
   • Spell 3 → Need potion ≥ 16/3 → 5.33 → index 1 → successful = 2
   • Spell 1 → Need potion ≥ 16/1 → 16 → index 3 → successful = 0
   • Spell 2 → Need potion ≥ 16/2 → 8 → index 1 → successful = 2

Output:

[2, 0, 2]

Complexity Analysis

The optimal approach is much faster and scales easily for input sizes up to 10⁵.

Key Takeaways

• Always sort the smaller array when possible to enable efficient binary search.
• Use integer ceiling division carefully when working with products and thresholds: long long minRequired = (success + spells[i] - 1) / spells[i];
• This problem is a great practice for binary search, sorting, and mathematical reasoning.

Final Thoughts

“Successful Pairs of Spells and Potions” is a beautiful blend of math and search optimization.
It teaches you how to think in terms of thresholds and efficient searching, which are key to mastering competitive programming.

If you found this helpful, consider sharing it with your fellow coders and saving it for your next DSA revision! 🚀