successful spells and potions. Leetcode problem: https://leetcode.com/problems/successful-pairs-of-spells-and-potions/description/
--------------------
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.
Intuition
My initial intuition (and I assume for many others out there), when seeing the problem, is to multiply each spell by each potion in the potions array, return the number of successful pairs and continue in this way. Unfortunately, this leads to a time complexity of O(n * m) which will not work for bigger inputs. In order to change the time complexity from O(n*m) to O(n * log(m)) we have to use a binary search to minimize the number of searches through the potions array we have to do.
Approach
We initiate a helper function called spellAndPotions which accepts a single spell, an array of potions and success/target number. It returns a number "successfulPairs" which is a counter for the number of successfulPairs of a single spell * potion in the potion array. The spellAndPotions function uses binary search in order to minimize the number of potions it has to analyze, therefore it expects the potions array to be sorted for the input.
successfulPairs function is initiated and accepts a spells array, potions array, and a success target number. In the function we first sort the potions array as this is what the helper function expects in order to be able to perform a binary search on the potions array. We then return an array by using map on each spell, so for each spell we call the spellAndPotions function on it, and for each spell we return the number of successful pairs for this spell vs all the potions in the potions array.
Binary search: The binary search algorithm in the function spellAndPotions initiates a left at the beginning of the array and right point at the end of the array, successfulPairs at 0 which is the counter. While left endpoint is less than or equal to right endpoint we have elements to search. In each iteration the algorithm calculates the middle point of the search. If this middle potion * spell is equal to or more than the success/target number, we add to the counter the number of elements from the middle element to the end of the array (right-mid are all the elements to the right + 1, the element we just checked). We also move the right counter to mid - 1, since everything to the right of mid is already assumed to be successful. Otherwise, we move the left counter to be mid + 1 because every potion on the left will be a smaller number and therefore will not product a successful match (there is simply no need to check them).
Complexity
-
Time complexity: O(n * log m)
-
Space complexity: O(1)
Code
function spellAndPotions(spell, potions, success) {
let left = 0;
let right = potions.length - 1;
let successfulPairs = 0;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (potions[mid] * spell >= success) {
successfulPairs += right - mid + 1;
right = mid - 1;
} else {
left = mid + 1;
}
}
return successfulPairs;
}
function successfulPairs(spells, potions, success) {
potions.sort((a, b) => a - b);
return spells.map((spell) => spellAndPotions(spell, potions, success));
}