Problem Statement in English

You’re given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the i-th spell and potions[j] represents the strength of the j-th potion.

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

You need to return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the i-th spell.

Approach

We can sort the potions array and for each spell, and use a binary search on potions to find the index of the minimum potion strength required to form a successful pair.

Solution in Python


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

        for i in range(len(spells)):
            target = ceil(success / spells[i])
            j = bisect_left(potions, target)

            res.append(l - j)

        return res

Complexity

  • Time: $O(n \log m + m \log m)$, where $n$ is the length of spells and $m$ is the length of potions.

This is because we sort potions which takes $O(m \log m)$ and for each spell, we do a binary search on potions which takes $O(\log m)$, leading to a total of $O(n \log m)$ for all spells.

  • Space: $O(1)$
    Since we use no additional space that grows with input size, the space complexity is $O(1)$.

And we are done.