Successful Pairs of Spells and Potions — Problem & Solution
Successful Pairs of Spells and Potions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Successful Pairs of Spells and Potions is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google and Razorpay interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Binary Search, Two Pointers
- Asked at: Amazon, Google, Razorpay
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A pair of a spell and a potion is successful when the product of their strengths is at least success.
Return an array whose i-th entry is the number of potions that form a successful pair with spell i.
Example 1
Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation: Spell 5 succeeds with potions 2, 3, 4 and 5.
Example 2
Input: spells = [3,1,2], potions = [8,5,8], success = 16
Output: [2,0,2]
Example 3
Input: spells = [1], potions = [1], success = 1
Output: [1]
Constraints
1 <= spells.length, potions.length <= 1000001 <= spells[i], potions[j] <= 1000001 <= success <= 1000000000
Hints for Successful Pairs of Spells and Potions
Hint 1
Sort the potions once, then answer each spell with a binary search.
Hint 2
For spell
s, the successful potions are those with strength at leastsuccess / s— a suffix of the sorted list.Hint 3
Compare with a multiplication rather than a division, so no rounding is involved.
How to solve Successful Pairs of Spells and Potions
Sorting the potions turns each spell's question into a lower-bound search: find the first potion whose product with this spell reaches success; everything after it works too.
Approach
- Sort
potionsascending. - For each spell
sp, binary search the first index wheresp · potions[mid] >= success. - The count is
potions.length - that index.
Why it works
For a fixed positive sp, the product is increasing in the potion's strength, so the successful potions form a suffix of the sorted array and the boundary is unique. Testing with a multiplication avoids the rounding trap of ceil(success / sp), which is easy to get wrong when the division is not exact.
Complexity
- Time —
O((n + m) log m) - Space —
O(m)
Pitfalls
spells[i] · potions[j]reaches10^5 · 10^5 = 10^10— the comparison needs 64-bit.- Dividing instead of multiplying needs a ceiling and rounds wrongly at exact multiples.
- The answer counts potions, so it is
m - index, not the index itself.
Reference solution
Python
from typing import List
def successfulPairs(spells: List[int], potions: List[int], success: int) -> List[int]:
sorted_potions = sorted(potions)
n = len(sorted_potions)
out = []
for sp in spells:
lo, hi = 0, n
while lo < hi:
mid = (lo + hi) // 2
if sp * sorted_potions[mid] >= success:
hi = mid
else:
lo = mid + 1
out.append(n - lo)
return outJava
public static int[] successfulPairs(int[] spells, int[] potions, int success) {
int[] sorted = potions.clone();
Arrays.sort(sorted);
int n = sorted.length;
int[] out = new int[spells.length];
for (int i = 0; i < spells.length; i++) {
long sp = spells[i];
int lo = 0, hi = n;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (sp * sorted[mid] >= success) hi = mid; else lo = mid + 1;
}
out[i] = n - lo;
}
return out;
}C++
vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, int success) {
vector<int> sorted = potions;
sort(sorted.begin(), sorted.end());
int n = (int) sorted.size();
vector<int> out;
for (int sp : spells) {
int lo = 0, hi = n;
while (lo < hi) {
int mid = (lo + hi) / 2;
if ((long long) sp * sorted[mid] >= success) hi = mid; else lo = mid + 1;
}
out.push_back(n - lo);
}
return out;
}JavaScript
var successfulPairs = function(spells, potions, success) {
var sorted = potions.slice().sort(function(a, b) { return a - b; });
var n = sorted.length;
var out = [];
for (var i = 0; i < spells.length; i++) {
var sp = spells[i];
var lo = 0, hi = n;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (sp * sorted[mid] >= success) hi = mid; else lo = mid + 1;
}
out.push(n - lo);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms