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.lengthm == potions.length1 <= n, m <= 1051 <= spells[i], potions[i] <= 1051 <= success <= 1010This approach involves iterating over each spell and checking the product with every potion to see if it exceeds the 'success' threshold. Though simple to understand and implement, this approach is inefficient for large input sizes due to its O(n * m) time complexity.
The function successfulPairs takes three parameters: spells, potions, and success. It iterates over each spell and computes the number of potions that can combine with it to meet the success criterion.
JavaScript
Time Complexity: O(n * m) where n is the number of spells and m is the number of potions.
Space Complexity: O(1) aside from the output list which requires O(n).
This approach leverages sorting and binary search for optimization. By sorting the potions array, for each spell, we can binary search to find the least potion that meets the success criterion, allowing us to efficiently count the valid potions.
We use Python's built-in bisect_left for binary searching the sorted potions array to find the first valid potion for each spell. The number of successful pairs is calculated by the count of potions at and beyond this index.
C++
Java
Time Complexity: O(m log m + n log m) due to sorting and binary searches.
Space Complexity: O(1) aside from space for the result list.
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force | Time Complexity: O(n * m) where n is the number of spells and m is the number of potions. |
| Approach 2: Sorting and Binary Search | Time Complexity: O(m log m + n log m) due to sorting and binary searches. |
Successful Pairs of Spells and Potions - Leetcode 2300 - Python • NeetCodeIO • 18,574 views views
Watch 9 more video solutions →Practice Successful Pairs of Spells and Potions with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor