We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Successful Pairs of Spells and Potions

Difficulty: Medium

Problem Description

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the i<sup>th</sup> spell and potions[j] represents the strength of the j<sup>th</sup> potion. You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success. Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the i<sup>th</sup> spell.

Key Insights

  • The brute force approach would involve checking every spell against every potion, which is inefficient for large inputs.
  • Sorting the potions array allows for efficient searching.
  • For each spell, we can determine the minimum potion strength required to achieve the success threshold using binary search.

Space and Time Complexity

Time Complexity: O(n log m) where n is the length of spells and m is the length of potions (due to sorting and binary search). Space Complexity: O(1) if we do not count the input and output storage.

Solution

The solution involves the following steps:

  1. Sort the potions array to facilitate efficient searching.
  2. For each spell, calculate the minimum potion strength required to reach the success threshold.
  3. Use binary search to find the first potion that meets or exceeds the required strength.
  4. The count of successful potions for each spell can be determined by the difference between the length of the potions array and the position found by binary search.

Code Solutions

def successfulPairs(spells, potions, success):
    # Sort the potions array for binary search
    potions.sort()
    n = len(spells)
    m = len(potions)
    pairs = []
    
    for spell in spells:
        # Calculate the minimum potion strength needed
        min_potion_strength = (success + spell - 1) // spell  # Equivalent to ceil(success / spell)
        
        # Binary search to find the first potion that is >= min_potion_strength
        left, right = 0, m
        while left < right:
            mid = (left + right) // 2
            if potions[mid] < min_potion_strength:
                left = mid + 1
            else:
                right = mid
                
        # The number of successful potions is the count of potions from left to end
        pairs.append(m - left)
    
    return pairs
← Back to All Questions