2300. Successful Pairs Of Spells And Potions

Summary

Solution Approach	Explanation (1-minute)	Time Complexity	Space Complexity
Brute Force	For each spell, check every potion to see if their product meets the success threshold. Count valid pairs by iterating through all spell-potion combinations.	\(O(n \cdot m)\) - Check each of \(n\) spells against each of \(m\) potions	\(O(1)\) - Only store counters and result array
Binary Search	Sort potions array, then for each spell find the minimum potion strength needed. Use binary search to find the first valid potion, then count remaining potions.	\(O(m \log m + n \log m)\) (Sort potions once, then binary search for each spell)	\(O(1)\) (Constant extra space excluding output array)

Implementation

PythonJavaScriptGo

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort() # O(m log m)
        result = []
        for s in spells: # O(n log m)
            l = 0
            r = len(potions) - 1

            # idx = float("inf")
            idx = len(potions)

            while l <= r:
                m = (l + r) // 2
                if s * potions[m] >= success:
                    r = m - 1
                    idx = m
                else:
                    l = m + 1

            # if idx == float("inf"):
            #     result.append(0)
            # else:
            #     result.append(len(potions)-idx)
            result.append(len(potions)-idx)
        return result