Successful Pairs of Spells and Potions

main.md

Question

Approach

I sort the potions array once. For each spell, I compute the minimum potion strength needed so that spell * potion >= success, which is needed = ceil(success / spell). Then I binary-search (bisect_left) in the sorted potions to find the first index with value >= needed; the number of successful potions for that spell is m - index.

Implementation

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()
        m = len(potions)
        res = []
        for s in spells:
            needed = (success + s - 1) // s
            idx = bisect.bisect_left(potions, needed)
            res.append(m - idx)
        return res

Complexities

• Time: O(mlogm + nlogm) — sorting potions costs 𝑂 ( 𝑚 log ⁡ 𝑚 ) ; each of the n binary searches costs 𝑂 ( log ⁡ 𝑚 )
• Space: O(1)