Successful Pairs of Spells and Potions — LeetCode 2300 Python Solution

The problem

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion. You are also given an integer success.

Example

Input

spells = [5,1,3], potions = [1,2,3,4,5], success = 7

Output

[4,0,3]

Explanation

- 0th spell: 5 * [1,2,3,4,5] = [5,10,15,20,25]. 4 pairs are successful.

Python solution

class Solution:
    def successfulPairs(
        self, spells: List[int], potions: List[int], success: int
    ) -> List[int]:
        potions.sort()
        m = len(potions)
        return [m - bisect_left(potions, success / v) for v in spells]

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 2300. Successful Pairs of Spells and Potions is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems