2300.Successful_Pairs_of_Spells_and_Potions(Medium).md

2300. Successful Pairs of Spells and Potions (Medium)

Date and Time: Nov 4, 2024, 11:41 (EST)

Link: https://leetcode.com/problems/successful-pairs-of-spells-and-potions/

Question:

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. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.

Example 1:

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.
- 1st spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
- 2nd spell: 3 * [1,2,3,4,5] = [3,6,9,12,15]. 3 pairs are successful.
Thus, [4,0,3] is returned.

Example 2:

Input: spells = [3,1,2], potions = [8,5,8], success = 16

Output: [2,0,2]

Explanation:
- 0th spell: 3 * [8,5,8] = [24,15,24]. 2 pairs are successful.
- 1st spell: 1 * [8,5,8] = [8,5,8]. 0 pairs are successful.
- 2nd spell: 2 * [8,5,8] = [16,10,16]. 2 pairs are successful.
Thus, [2,0,2] is returned.

Constraints:

• n == spells.length

• m == potions.length

• 1 <= n, m <= 10^5

• 1 <= spells[i], potions[i] <= 10^5

• 1 <= success <= 10^10

Walk-through:

1. Sort potions, so we can run Binary Search to find a smallest left pointer.

2. Run Binary Search on potions to find the smallest left pointer. We compare the product (spell * potions[m]), if the product >= success, we should decrement r = m - 1, so we can find the smallest k. Otherwise, we should increment l = m + 1.

Don't forget to reset k, and l, r pointers after we finish a spell.

Python Solution:

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        # 1. Sort potions
        # 2. Run BS on potions by calculating product of spells[i] * potions[j] to find smallest l
        # r will always be the end of potions
        # Adjust l, r depends on the product, if product >= success, decrement r = m - 1
        # If product < success, increment l = m + 1
        # 3. Append (len(potions) - lowest_l) or 0 into res[]

        # [0, 4], m = 2, 15 > 7, decrement r
        # [0, 1], m = 0, 5 < 7, increment l
        # [1, 1], m = 1, 10 > 7, decrement r
        # [1, 0], break the while loop

        # TC: O(mlogm + n * logm), SC: O(n)
        potions.sort()
        res = []
        for i in spells:
            k = float("inf")    # Check if a product > success exists or not
            l, r = 0, len(potions)-1
            # Run Binary Search on Potions for each spell
            while l <= r:
                m = (l + r) // 2
                # If product >= success, update k and decrement r = m - 1
                if i * potions[m] >= success:
                    k = min(k, m)
                    r = m - 1
                # If product < success, increment l = m + 1
                else:
                    l = m + 1
            # Append 0 if we couldn't find any index of product >= success
            if k == float("inf"):
                res.append(0)
            else:
                res.append(len(potions)-k)
        
        return res

Time Complexity: $O(mlogm + n*logm)$, we first sort potions by $O(mlogm)$, then for each spell we run binary search on potions to find the smallest left pointer, which takes $O(nlogm)$.
Space Complexity: $O(n)$, the array we return will only have length of spells.