Problem of The Day: Successful Pairs of Spells and Potions
Problem Statement
My Solution [TLE]
class Solution:
def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
sorted_potions = sorted(potions)
len_potions = len(sorted_potions)
last_index = len(sorted_potions) - 1
res = []
for spell in spells:
arr = [spell * potion for potion in sorted_potions]
idx = float('inf')
l, r = 0, len_potions - 1
while l <= r:
mid = l + (r - l) // 2
if arr[mid] > success:
idx = mid
r = mid - 1
elif arr[mid] < success:
l = mid + 1
else:
idx = mid
r = mid - 1
num_of_pairs = last_index - idx + 1
if num_of_pairs > 0:
res.append(num_of_pairs)
else:
res.append(0)
return res
Improved Algorithm [Accepted]
Instead of the list arr, use curr = sorted_potions[mid] * spell to prevent from creating the list which requires O(N) time and space.
class Solution:
def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
sorted_potions = sorted(potions)
len_potions = len(sorted_potions)
last_index = len(sorted_potions) - 1
res = []
for spell in spells:
idx = float('inf')
l, r = 0, len_potions - 1
while l <= r:
mid = l + (r - l) // 2
curr = sorted_potions[mid] * spell
if curr > success:
idx = mid
r = mid - 1
elif curr < success:
l = mid + 1
else:
idx = mid
r = mid - 1
num_of_pairs = last_index - idx + 1
if num_of_pairs > 0:
res.append(num_of_pairs)
else:
res.append(0)
return res
Editorial
Approach 1: Sorting + Binary Search
class Solution:
def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
# Sort the potions array in increasing order.
potions.sort()
answer = []
m = len(potions)
maxPotion = potions[m - 1]
for spell in spells:
# Minimum value of potion whose product with current spell
# will be at least success or more.
minPotion = (success + spell - 1) // spell
# Check if we don't have any potion which can be used.
if minPotion > maxPotion:
answer.append(0)
continue
# We can use the found potion, and all potion in its right
# (as the right potions are greater than the found potion).
index = bisect.bisect_left(potions, minPotion)
answer.append(m - index)
return answer
Approach 2: Sorting + Two Pointers
class Solution:
def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
sortedSpells = [(spell, index) for index, spell in enumerate(spells)]
# Sort the 'spells with index' and 'potions' array in increasing order.
sortedSpells.sort()
potions.sort()
answer = [0] * len(spells)
m = len(potions)
potionIndex = m - 1
# For each 'spell' find the respective 'minPotion' index.
for spell, index in sortedSpells:
while potionIndex >= 0 and (spell * potions[potionIndex]) >= success:
potionIndex -= 1
answer[index] = m - (potionIndex + 1)
return answer