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 <= 1010Problem Overview: You are given two arrays: spells and potions. A pair is successful if spells[i] * potions[j] >= success. For each spell, compute how many potions form a successful pair.
Approach 1: Brute Force (O(n * m) time, O(1) space)
The most direct solution checks every possible pair. For each value in spells, iterate through the entire potions array and compute the product. If the product meets or exceeds success, increment the count for that spell. This approach uses two nested loops and performs a multiplication check for every pair.
The implementation is straightforward and useful for validating logic or small inputs. However, it becomes slow when both arrays are large because the algorithm evaluates n * m combinations. With constraints in the tens of thousands, this approach easily times out.
Approach 2: Sorting and Binary Search (O(n log m + m log m) time, O(1) extra space)
A more efficient solution sorts the potions array first. Once sorted, you can determine the minimum potion value needed for a spell to succeed. For a spell value s, the requirement is s * potion >= success, which implies potion >= ceil(success / s). Instead of scanning the entire array, perform a binary search to find the first potion meeting this threshold.
After locating the first valid index, every potion to the right of it will also work because the array is sorted. The count becomes len(potions) - index. Repeat this process for each spell. Sorting is done once, then each spell query runs in logarithmic time.
This approach combines sorting with binary search to avoid redundant comparisons. The idea of converting the inequality into a searchable threshold is the key insight. You never explicitly test every pair.
Recommended for interviews: The sorting + binary search approach is what interviewers expect. The brute force solution shows you understand the pairing requirement, but the optimized version demonstrates familiarity with array preprocessing and logarithmic search techniques. Recognizing that the inequality can be turned into a lower bound search is the core skill being tested.
This 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.
Python
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.
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.
We can sort the potion array, then traverse the spell array. For each spell v, we use binary search to find the first potion that is greater than or equal to \frac{success}{v}. We mark its index as i. The length of the potion array minus i is the number of potions that can successfully combine with this spell.
The time complexity is O((m + n) times log m), and the space complexity is O(log n). Here, m and n are the lengths of the potion array and the spell array, respectively.
| 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. |
| Sorting + Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n * m) | O(1) | Small inputs or when first verifying the pairing logic |
| Sorting + Binary Search | O(m log m + n log m) | O(1) | Large arrays where efficient lookups are required for each spell |
Successful Pairs of Spells and Potions - Leetcode 2300 - Python • NeetCodeIO • 24,009 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