Watch 10 video solutions for Successful Pairs of Spells and Potions, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by NeetCodeIO has 24,009 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |