Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

For a fixed positive spell strength, successful potions form a suffix of the sorted potion array. Finding that suffix's first index immediately gives the count, and identical spells can reuse the same boundary.

Approach

Sort the potions. For each distinct spell, binary-search the first potion whose product with the spell is at least success: move left on a successful midpoint and right otherwise. Its count is potionCount - boundary, including zero when the boundary lies past the end. Cache this result or boundary by spell strength, then emit counts in the original spell order. Direct product comparison preserves the inclusive threshold without rounding a quotient.

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int ) -> List[int]:
        m = len(potions)
        potions.sort()

        @cache
        def bs(s):
            l = 0
            r = m - 1

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

            return l

        res = []

        for s in spells:
            res.append(m - bs(s))

        return res

Complexity analysis

Let s = spells.length, m = potions.length, and d be the number of distinct spell strengths. Both displayed implementations sort the potions and cache one binary-search result per distinct spell, taking O(m log m + d log m + s) time and O(d) auxiliary cache space, plus the runtime's potion-sort workspace and the returned O(s) list.