Successful Pairs of Spells and Potions

Info

I slowed down too much on this problem since I was trying to add too many optimizations at once. Take one at a time.

Improvement

• Improved by sorting and then not processing based on the idea that if the product of a number multiplied by another number is >= target, a lesser number can start at the positions that are candidates for that number.
• Also, you don’t have to process the rest of a number against the potions since you know the numbers after it will also create a valid potion (larger numbers multiplied by each other)

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        sorted_spells = sorted(spells, reverse=True)
        sorted_potions = sorted(potions)
        n, m = len(spells), len(potions)
        d = defaultdict(int)
        prev_count = m
 
        for i in range(n):
            for j in range(m - prev_count, m):
                if sorted_spells[i] * sorted_potions[j] >= success:
                    d[sorted_spells[i]] = m - j
                    break
            prev_count = d[sorted_spells[i]]
 
        res = [0] * n
        for i, spell in enumerate(spells):
            res[i] += d[spell]
        
        return res

Brute Force

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        res = [0] * len(spells)
 
        for i, spell in enumerate(spells):
            for potion in potions:
                if spell * potion >= success:
                    res[i] += 1
        return res
        

1st Attempt

---

References

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