blog

Leetcode 2300. Successful Pairs of Spells and Potions

Date: 2025-10-08

---

Content

Problem Link: Leetcode 2300. Successful Pairs of Spells and Potions

import java.util.Arrays;

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int n = potions.length;
        int[] res = new int[spells.length];

        for (int i = 0; i < spells.length; i++) {
            int left = 0, right = n - 1;
            int idx = n;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if ((long)spells[i] * potions[mid] >= success) {
                    idx = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            res[i] = n - idx;
        }
        return res;
    }
}

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<int> successfulPairs(std::vector<int>& spells, std::vector<int>& potions, long long success) {
        std::sort(potions.begin(), potions.end());
        int n = potions.size();
        std::vector<int> res;
        for (int spell : spells) {
            int left = 0, right = n - 1, idx = n;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if ((long long)spell * potions[mid] >= success) {
                    idx = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            res.push_back(n - idx);
        }
        return res;
    }
};

Explanation

• Sorting: The potions array is sorted to enable binary search.
• Binary Search: For each spell, binary search is used to find the first potion such that spell * potion >= success.
• The number of successful pairs for each spell is the count of potions from this index to the end of the potions array.
• This approach is efficient, running in O(m log n) time, where m is the number of spells and n is the number of potions.

---

Reference: Gemini Shared Content