2300. Successful Pairs of Spells and Potions

Problem Statement

link: LeetCode.cn LeetCode You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.

Example:

Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7 Output: [4,0,3]

Input: spells = [3,1,2], potions = [8,5,8], success = 16 Output: [2,0,2]

Solution Approach

The solution involves sorting the potions and using binary search to efficiently count how many potions can pair with each spell to meet or exceed the success threshold.

Algorithm

1. Sorting Potions: Sort the potions array to enable efficient binary search, which helps in quickly finding the threshold potion strength required for a successful pair with each spell.
2. Binary Search: For each spell, use binary search to find the first potion whose strength, when multiplied by the spell’s strength, meets or exceeds the success threshold.
3. Counting Successful Pairs: Calculate the number of successful pairs for each spell by determining the number of potions from the found position to the end of the potions array and store these counts in the result array.

Implement

    class Solution:
        def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        # spells = sorted([(s, i) for i, s in enumerate(spells)])
        # potions.sort()
        # res = [0] * len(spells)
        # m = len(potions)
        # j = m - 1
        # for spell, i in spells:
        #     while j >= 0 and (spell * potions[j]) >= success:
        #         j -= 1
        #     res[i] = m - (j + 1)
        # return res
        potions.sort()
        res = []
        m = len(potions)
        for s in spells:
            i = bisect.bisect_left(potions, math.ceil(success / s))
            res.append(m - i)
        return res

    //java code
import java.util.HashMap;
import java.util.Map;

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

        List<int[]> spellIndexPairs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            spellIndexPairs.add(new int[]{spells[i], i});
        }

        Collections.sort(spellIndexPairs, (a, b) -> a[0] - b[0]);
        Arrays.sort(potions);

        int j = m - 1;
        for (int[] pair: spellIndexPairs) {
            int spell = pair[0];
            int index = pair[1];

            while (j >= 0 && (long) spell * potions[j] >= success) {
                j--;
            }
            
            res[index] = m - (j + 1);//notice here is not m - j
        }
        return res;
    }
}

    

Twitter  facebook  Email