Successful Pairs of Spells and Potions solution and explanation
Google
9 more videos on this problem
Successful Pairs of Spells and Potions - Leetcode 2300 - PythonNeetCodeIO · 14:28 · 24K views
Successful Pairs of Spells and Potions | Leetcode 2300 | Detailed | codestorywithMIKcodestorywithMIK · 35:05 · 12K views
Successful Pairs of Spells and Potions || Binary Search || With & Without Libraries || C++/Java/PyAryan Mittal · 12:33 · 2K views
Successful Pairs of Spells and Potions - LeetCode 2300 - Python #leetcode #leetcode75Deepti Talesra · 11:33 · 1K views
2300. Successful Pairs of Spells and Potions (Leetcode Medium)Programming Live with Larry · 6:53 · 1K views
2300. Successful Pairs of Spells and Potions | LeetCode Daily Challenge | LeetCode POTDDeep Tech · 15:38 · 980 views
Daily Leetcode #1097: Apr 02, 2023 - 2300. Successful Pairs of Spells and PotionsProgramming Live with Larry · 7:47 · 689 views
Successful Pairs of Spells and Potions - Leetcode 2300 - PythonTechError · 8:05 · 536 views
2300. Successful Pairs of Spells and Potions(leetcode) solved by two approach in java.Code_with_Aman$$. · 17:53 · 309 views
2300. Successful Pairs of Spells and Potions | Leetcode Daily - PythonLeetcode Daily · 7:53 · 300 views
The problem
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 <= 1010
Approach overview
Problem 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 1: Approach 1: Brute Force
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.
def successfulPairs(spells, potions, success):
n = len(spells)
pairs = [0] * n
for i in range(n):
count = 0
for potion in potions:
if spells[i] * potion >= success:
count += 1
pairs[i] = count
return pairsfunction successfulPairs(spells, potions, success) {
const n = spells.length;
const pairs = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
let count = 0;
for (let j = 0; j < potions.length; j++) {
if (spells[i] * potions[j] >= success) {
count++;
}
}
pairs[i] = count;
}
return pairs;
}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.
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).
Approach 2: Approach 2: Sorting and Binary Search
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.
from bisect import bisect_left
def successfulPairs(spells, potions, success):
potions.sort()
n = len(spells)
m = len(potions)
pairs = []
for spell in spells:
min_potion = (success + spell - 1) // spell # ceiling of success / spell
index = bisect_left(potions, min_potion)
pairs.append(m - index)
return pairsimport java.util.Arrays;
public class Solution {
public int[] successfulPairs(int[] spells, int[] potions, long success) {
Arrays.sort(potions);
int n = spells.length;
int m = potions.length;
int[] result = new int[n];
for (int i = 0; i < n; i++) {
int left = 0, right = m;
long minPotency = (success + spells[i] - 1) / spells[i];
while (left < right) {
int mid = left + (right - left) / 2;
if (potions[mid] >= minPotency) {
right = mid;
} else {
left = mid + 1;
}
}
result[i] = m - left;
}
return result;
}
}#include <vector>
#include <algorithm>
using namespace std;
vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
sort(potions.begin(), potions.end());
int n = spells.size();
int m = potions.size();
vector<int> results(n, 0);
for (int i = 0; i < n; ++i) {
long long minPotionStrength = (success + spells[i] - 1) / spells[i];
int index = lower_bound(potions.begin(), potions.end(), minPotionStrength) - potions.begin();
results[i] = m - index;
}
return results;
}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.
Approach 3: Sorting + Binary Search
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.
function successfulPairs(spells: number[], potions: number[], success: number): number[] {
potions.sort((a, b) => a - b);
const m = potions.length;
const ans: number[] = [];
for (const v of spells) {
const targetPotion = success / v;
const idx = _.sortedIndexBy(potions, targetPotion, p => p);
ans.push(m - idx);
}
return ans;
}func successfulPairs(spells []int, potions []int, success int64) (ans []int) {
sort.Ints(potions)
m := len(potions)
for _, v := range spells {
i := sort.Search(m, func(i int) bool { return int64(potions[i]*v) >= success })
ans = append(ans, m-i)
}
return ans
}impl Solution {
pub fn successful_pairs(spells: Vec<i32>, mut potions: Vec<i32>, success: i64) -> Vec<i32> {
potions.sort();
let m = potions.len();
let mut ans = Vec::with_capacity(spells.len());
for &v in &spells {
let target = (success + v as i64 - 1) / v as i64;
let idx = potions.partition_point(|&p| (p as i64) < target);
ans.push((m - idx) as i32);
}
ans
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Successful Pairs of Spells and Potions easy or hard?
The problem is rated Medium because the brute force idea is simple but inefficient. The challenge is recognizing that the inequality can be converted into a threshold and solved using sorting and binary search. Candidates comfortable with search boundaries and array preprocessing usually solve it quickly.
Successful Pairs of Spells and Potions Python/Java solution
Most implementations first sort the potions array, then loop through each spell and apply binary search to find the minimum potion index satisfying spell * potion >= success. Python commonly uses bisect, while Java and C++ implement lower_bound style binary search. Each spell result is computed in O(log m).
How to solve Successful Pairs of Spells and Potions in O(n)?
An exact O(n) solution is not typical unless the potions array is already sorted and constraints allow linear scanning with two pointers. In the general case, sorting followed by binary search is used. That approach runs in O(m log m + n log m), which is efficient for arrays up to 10^5 elements.
What is the best approach for Successful Pairs of Spells and Potions?
The optimal approach sorts the potions array and then performs a binary search for each spell. For a spell value s, compute the minimum potion value required as ceil(success / s). Binary search finds the first potion meeting that threshold, and all elements to the right are valid pairs. The overall complexity becomes O(m log m + n log m).
Is Successful Pairs of Spells and Potions asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving sorting and binary search on arrays. Variations of threshold search problems appear in interviews at companies like Amazon, Google, and Meta, where candidates must convert a condition into a searchable boundary in a sorted structure.
What data structure is used in Successful Pairs of Spells and Potions?
The core data structures are arrays for storing spells and potions. The optimized solution relies on sorting the potions array and applying binary search to locate the first valid potion for each spell. No additional complex structures like heaps or hash maps are required.
What is the time complexity of Successful Pairs of Spells and Potions?
The brute force approach runs in O(n * m) time because every spell is multiplied with every potion. The optimized solution sorts the potions array in O(m log m) time and performs a binary search for each spell in O(log m). This results in a total complexity of O(m log m + n log m) with constant extra space.