Sponsored
Sponsored
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.
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).
1function successfulPairs(spells, potions, success) {
2 const n = spells.length;
3 const pairs = new Array(n).fill(0);
4 for (let i = 0; i < n; i++) {
5 let count = 0;
6 for (let j = 0; j < potions.length; j++) {
7 if (spells[i] * potions[j] >= success) {
8 count++;
9 }
10 }
11 pairs[i] = count;
12 }
13 return pairs;
14}The method iterates over each spell and checks each potion to see if their product is at least as large as the value of success. Each successful spell-potion pair increments the count for that spell.
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.
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.
1from bisect import bisect_left
2
3We 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.