2300. Successful Pairs of Spells and Potions
Problem Description
In this problem, you are provided with two arrays called spells
and potions
. The spells
array contains elements representing the strength of each spell, and similarly, the potions
array contains elements representing the strength of each potion. The task is to determine for each spell, how many potions can successfully combine with it to achieve or exceed a given success
threshold. A spell and potion pair is deemed successful if the product (multiplication) of their strengths is at least equal to the success
value provided. You should return an array where each value corresponds to the number of successful potion combinations for each spell in the spells
array.
To clarify with an example, suppose spells = [10, 20]
, potions = [5, 8, 10]
, and success = 100
. To find successful pairs, you multiply each spell with each potion:
- For the first spell (strength 10), it pairs successfully with two potions (potions of strength 10 and 8) since both products are at least 100.
- For the second spell (strength 20), it pairs successfully with all three potions, as all products will be 100 or greater.
The result array will be
[2, 3]
as the first spell has 2 successful combinations, and the second has 3.
Intuition
The goal is to find an efficient way to pair spells with potions such that the product of their strengths is at least the success target. A brute-force approach would be to try all possible pairs, but this can be inefficient, especially with large arrays.
Instead, by first sorting the potions
array, we can take advantage of binary search to quickly find the number of successful potions for each spell. Binary search operates by repeatedly dividing the search interval in half, which is much faster than scanning every element.
Once the potions
array is sorted, for each spell, we want to find the position where the potion strength is just enough or more to meet the success
target when paired with the spell. We need to find the smallest potion that, when multiplied by the spell's strength, equals or exceeds the success
threshold. All potions to the right in the sorted array are guaranteed to also form successful pairs because they are equal or stronger.
The solution leverages the bisect_left
function from Python's bisect
module, which uses binary search to find the insertion point for a given element to maintain sorted order. In this context, it finds the first index in potions
where the potion strength is sufficient for the success
criteria with a given spell. We then subtract this index from the total number of potions (m
) to get the count of successful potions for that spell.
For each spell in spells
, we apply this logic and generate the final result array.
Learn more about Two Pointers, Binary Search and Sorting patterns.
Solution Approach
The solution implements a binary search mechanism to optimize the process of finding successful spell-potion pairs. Here's a step-wise explanation of the approach used in the solution:
-
Sorting the Potions: Begin by sorting the
potions
array. This is crucial for binary search to work since binary search requires a sorted array to function correctly. Sorting is done in ascending order. -
Using Binary Search: For each spell's strength value, we apply a binary search to determine the number of potions that, when multiplied by this spell's strength, will at least be equal to the
success
value. This is done by finding the leftmost (smallest) potion index that can achieve the required target when combined with the current spell. -
Calculating Successful Pairs:
- We use the
bisect_left
function which finds the index at which we could insert the valuesuccess / spell_strength
intopotions
to maintain sorted order. - The value we are searching for is calculated by
success / spell_strength
because we want to find the potion strength that, at the minimum, when multiplied by the spell's strength, is equal tosuccess
. - Since
potions
is sorted, every potion at and beyond the index returned bybisect_left
would result in a successful pair when combined with the current spell.
- We use the
-
Storing Results:
- For each spell, we calculate
m - index
to find out the number of successful potions, wherem
is the total number of potions andindex
is the position returned bybisect_left
. - This operation gives us the count because all elements from the position
index
to the end of the potions array will be successful pairs due to the sorted property of the array.
- For each spell, we calculate
-
Generating the Output: Finally, we return a list comprehension that iterates over every spell in
spells
, applies the above logic usingbisect_left
, and calculates the number of successful pairs for that spell.
Here's the critical code snippet with explanations for clarity:
potions.sort() # Step 1: [Sorting](/problems/sorting_summary) the 'potions' array.
m = len(potions) # Storing the length of the 'potions' array.
# Step 2, 3, and 4: List comprehension iterating over 'spells'.
return [m - bisect_left(potions, success / v) for v in spells]
Through sorting and binary searching, this algorithm achieves a complexity of O(n log m)
, where n
is the number of spells, and m
is the number of potions. Sorting takes O(m log m)
, and then each binary search operation takes O(log m)
, with the linear iteration over spells
representing the n
in the complexity.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example based on the solution approach given above.
Consider we have spells = [15, 10]
, potions = [1, 5, 20, 8]
, and success = 120
. We aim to determine for each spell, how many potions achieve or exceed the success
threshold when multiplied by the spell.
-
Sorting the Potions: The first step is sorting the
potions
array. Before:[1, 5, 20, 8]
After sorting:[1, 5, 8, 20]
-
Using Binary Search: We then apply binary search to find the count of potions that can pair with a spell to achieve the
success
.- For spell
15
: We search for the smallest potion that when multiplied is at least120
. That potion should be120 / 15 = 8
. - For spell
10
: We need a potion of at least120 / 10 = 12
.
- For spell
-
Calculating Successful Pairs:
- For spell
15
: Usingbisect_left
, we find the index where8
could fit in the sortedpotions
array[1, 5, 8, 20]
, which is index2
. - For spell
10
: Usingbisect_left
, we find the index where12
could fit, which is after8
and before20
. Hence, the index would be3
.
- For spell
-
Storing Results:
- For spell
15
:m - index
is4 - 2 = 2
. So, there are 2 successful potion combinations for the spell15
. - For spell
10
:m - index
is4 - 3 = 1
. Therefore, there is 1 successful potion combination for the spell10
.
- For spell
-
Generating the Output: According to the steps described in the solution approach, we create a list with the counts of successful combinations for each spell. The result for our example will be
[2, 1]
.
For better understanding, here's how the binary search part of the code would operate in a step-by-step manner:
-
Spell is
15
:bisect_left([1, 5, 8, 20], 120/15)
-
It finds the position of
8
because8 * 15
is exactly120
. -
index = 2
, total potionsm = 4
, successful combinations:4 - 2 = 2
. -
Spell is
10
:bisect_left([1, 5, 8, 20], 120/10)
-
It passes over
8
(since8 * 10
is less than120
) and settles before20
. -
index = 3
, successful combinations:4 - 3 = 1
.
Thus, the final returned value for this particular example with the spells
and potions
given would be [2, 1]
. Each spell has a corresponding count of potions that, when multiplied, meet or exceed the success
threshold.
Solution Implementation
1from bisect import bisect_left
2from typing import List
3
4class Solution:
5 def successful_pairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
6 """
7 Find the number of potions for each spell that when combined
8 result in a product equal to or greater than the success threshold.
9
10 Args:
11 spells: List of integers representing the strength of spells.
12 potions: List of integers representing the volume of potions.
13 success: An integer representing the minimum success threshold for a spell-potion combination.
14
15 Returns:
16 List containing the count of successful potion combinations for each spell.
17 """
18 # Sort the potions list in ascending order for binary searching
19 potions.sort()
20
21 # Length of the potions list
22 num_potions = len(potions)
23
24 # Using list comprehension to generate the list of counts for successful combinations
25 # For each spell strength 'spell_strength' in 'spells', we find the index of the first potion
26 # in the sorted 'potions' list that meets or exceeds the 'success' threshold when combined with the spell.
27 # The count of successful pairings for each spell is then the total number of potions
28 # minus this index, giving the number of potions that meet or exceed the product threshold.
29 return [num_potions - bisect_left(potions, success / spell_strength) for spell_strength in spells]
30
1import java.util.Arrays; // Ensure to import the necessary Arrays class for sorting.
2
3class Solution {
4
5 // This function determines the number of successful pairs of spells and potions.
6 public int[] successfulPairs(int[] spells, int[] potions, long successThreshold) {
7 Arrays.sort(potions); // Sort the potions array for binary search.
8 int nSpells = spells.length; // Number of spells.
9 int nPotions = potions.length; // Number of potions.
10 int[] successfulPairs = new int[nSpells]; // Array to store the answer.
11
12 // Iterate over each spell.
13 for (int i = 0; i < nSpells; ++i) {
14 int left = 0, right = nPotions; // Set search boundaries for binary search.
15
16 // Binary search to find the first potion that results in a successful pair.
17 while (left < right) {
18 int mid = (left + right) / 2; // Calculate the mid index.
19 // Check if the current spell and potion at mid index is a successful pair.
20 if ((long) spells[i] * potions[mid] >= successThreshold) {
21 right = mid; // If successful, narrow the search to the left half.
22 } else {
23 left = mid + 1; // If not successful, narrow the search to the right half.
24 }
25 }
26
27 // The number of successful pairs for the current spell is the total number
28 // of potions minus the number of potions that did not meet the success threshold.
29 successfulPairs[i] = nPotions - left;
30 }
31 return successfulPairs; // Return the array of successful pair counts.
32 }
33}
34
1class Solution {
2public:
3 // Function to find the number of successful pairs
4 vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
5 // Sort the potions array for binary search
6 sort(potions.begin(), potions.end());
7
8 // ans will hold the answer to the problem
9 vector<int> ans;
10
11 // m is the size of the potions array
12 int m = potions.size();
13
14 // Iterate over each spell
15 for (int spell : spells) {
16 // Find the first potion that, when multiplied with the spell,
17 // is greater than or equal to the success threshold.
18 // We use 1.0 to cast success to double for correct division.
19 int index = lower_bound(potions.begin(), potions.end(), (success + spell - 1) / spell) - potions.begin();
20
21 // Push the number of successful pairs into the answer vector.
22 // Subtract the found index from the size to determine the number of successful potions.
23 ans.push_back(m - index);
24 }
25
26 // Return the final answer
27 return ans;
28 }
29};
30
1function successfulPairs(spells: number[], potions: number[], successThreshold: number): number[] {
2 // Sort the potions array in ascending order
3 potions.sort((a, b) => a - b);
4
5 // The number of potions available
6 const potionCount = potions.length;
7
8 // Initialize an array to store the number of successful pairs for each spell
9 const successfulPairsCount: number[] = [];
10
11 // Iterate over each spell
12 for (const spell of spells) {
13 // Set the initial bounds for binary search
14 let left = 0;
15 let right = potionCount;
16
17 // Perform binary search to find the index where
18 // spell * potionValue is greater than or equal to success threshold
19 while (left < right) {
20 // Calculate the middle index
21 const mid = Math.floor((left + right) / 2);
22
23 // Check if the current combination meets the success requirement
24 if (spell * potions[mid] >= successThreshold) {
25 // If it does, we need to find if there's a smaller index that also satisfies the condition
26 right = mid;
27 } else {
28 // If not, move the left pointer to narrow the search
29 left = mid + 1;
30 }
31 }
32
33 // The number of potions that meet the success criteria with the current spell
34 // is the length of the potions array minus the left bound found by binary search
35 successfulPairsCount.push(potionCount - left);
36 }
37
38 // Return the array containing the counts of successful spell-potion pairs
39 return successfulPairsCount;
40}
41
Time and Space Complexity
Time Complexity
The time complexity of the given code snippet consists of two parts: sorting the potions
list and performing binary searches using the bisect_left
function.
- Sorting: The
potions.sort()
operation has a time complexity ofO(n log n)
wheren
is the number of potions. - Binary Search: The binary search inside the list comprehension using
bisect_left
is performed for each spell. If there ares
spells, and the binary search has a time complexity ofO(log n)
for each spell, the entire list comprehension has a time complexity ofO(s log n)
.
Therefore, combining both operations, the total time complexity is O(n log n + s log n)
.
Space Complexity
The space complexity is determined by the additional space required beyond the input data.
- Sorting Space: The sorting is done in place, which does not require additional space, so it's
O(1)
. - Output List: There is a list comprehension that generates a list of the same length as the number of spells. Therefore, it has a space complexity of
O(s)
wheres
is the number of spells.
Given that O(s)
is the larger term between O(1)
and O(s)
, the overall space complexity is O(s)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following shows the order of node visit in a Breadth-first Search?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Want a Structured Path to Master System Design Too? Donāt Miss This!