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).
1def successfulPairs(spells, potions, success):
2 n = len(spells)
3 pairs = [0] * n
4 for i in range(n):
5 count = 0
6 for potion in potions:
7 if spells[i] * potion >= success:
8 count += 1
9 pairs[i] = count
10 return pairsThe 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.
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.