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.
1import java.util.Arrays;
2
Java's implementation uses manual binary search to find the lower bound for the required potion strength, allowing it to efficiently determine the number of successful pairs for each spell.