Successful Pairs of Spells and Potions

Medium

Amazon

2 views

Topics:

ArraysBinary Search

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth 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 ith spell.

For example:

spells = [5, 1, 3], potions = [1, 2, 3, 4, 5], success = 7

The output should be [4, 0, 3] because:

0^th spell: 5 * [1, 2, 3, 4, 5] = [5, **10**, **15**, **20**, **25**]. 4 pairs are successful.
1^st spell: 1 * [1, 2, 3, 4, 5] = [1, 2, 3, 4, 5]. 0 pairs are successful.
2^nd spell: 3 * [1, 2, 3, 4, 5] = [3, 6, **9**, **12**, **15**]. 3 pairs are successful.

As another example:

spells = [3, 1, 2], potions = [8, 5, 8], success = 16

The output should be [2, 0, 2] because:

0^th spell: 3 * [8, 5, 8] = [**24**, 15, **24**]. 2 pairs are successful.
1^st spell: 1 * [8, 5, 8] = [8, 5, 8]. 0 pairs are successful.
2^nd spell: 2 * [8, 5, 8] = [**16**, 10, **16**]. 2 pairs are successful.

Can you implement an algorithm to solve this?

Successful Pairs of Spells and Potions

Medium

Amazon

2 views

Topics:

ArraysBinary Search

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth 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 ith spell.

For example:

spells = [5, 1, 3], potions = [1, 2, 3, 4, 5], success = 7

The output should be [4, 0, 3] because:

0^th spell: 5 * [1, 2, 3, 4, 5] = [5, **10**, **15**, **20**, **25**]. 4 pairs are successful.
1^st spell: 1 * [1, 2, 3, 4, 5] = [1, 2, 3, 4, 5]. 0 pairs are successful.
2^nd spell: 3 * [1, 2, 3, 4, 5] = [3, 6, **9**, **12**, **15**]. 3 pairs are successful.

As another example:

spells = [3, 1, 2], potions = [8, 5, 8], success = 16

The output should be [2, 0, 2] because:

0^th spell: 3 * [8, 5, 8] = [**24**, 15, **24**]. 2 pairs are successful.
1^st spell: 1 * [8, 5, 8] = [8, 5, 8]. 0 pairs are successful.
2^nd spell: 2 * [8, 5, 8] = [**16**, 10, **16**]. 2 pairs are successful.

Can you implement an algorithm to solve this?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values within the `spells` and `potions` arrays? Can these values be negative, zero, or floating-point numbers?
What is the expected behavior if the product of a spell and potion exceeds the `success` value, or if it equals the `success` value? Should I only count products strictly greater than `success`?
Can the input arrays, `spells` or `potions`, be empty or null? If so, what should the return value be in those cases?
Are there any constraints on the size of the `spells` and `potions` arrays? I'm thinking about potential memory usage.
Is the order of the output array important? For each spell, am I expected to return the count of successful potions at the same index?

Brute Force Solution

Approach

The brute force method for this problem involves checking every single possible combination of spells and potions. For each spell, we'll go through every potion to see if they work together to meet a certain requirement. We simply count the successful pairings that meet this requirement.

Here's how the algorithm would work step-by-step:

Take the first spell from the list of spells.
Now, one by one, compare this spell against every potion in the potion list.
For each spell and potion combination, check if their product meets the given success requirement.
If the product meets or exceeds the success requirement, mark that spell and potion as a successful pair.
Keep a running total of the number of successful pairs for this specific spell.
After checking the first spell against all the potions, move on to the second spell.
Repeat the process: compare the second spell against every potion, checking for successful pairs and updating the count.
Continue this process for every spell in the list, ensuring each spell is checked against all potions.
After processing all spells, you will have a list showing how many successful potion pairings each spell has.

Code Implementation

def successful_pairs_brute_force(spells, potions, success):
    number_of_spells = len(spells)
    number_of_potions = len(potions)
    successful_pairs = []

    for i in range(number_of_spells):
        spell = spells[i]
        pairs_for_current_spell = 0

        #Iterate through each potion for the current spell
        for j in range(number_of_potions):
            potion = potions[j]

            #Checking if spell and potion are a successful pair
            if (spell * potion) >= success:
                pairs_for_current_spell += 1

        successful_pairs.append(pairs_for_current_spell)

    return successful_pairs

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each spell in the spells array (size m). For each spell, it then iterates through every potion in the potions array (size n). Inside the inner loop, a constant time operation (multiplication and comparison) is performed. Therefore, the dominant operations consist of checking every possible spell-potion pair, resulting in m * n operations in the worst case. Thus, the overall time complexity is O(m*n).

Space Complexity

O(1) – The brute force approach iterates through the spells and potions, counting successful pairs for each spell. It does not create any auxiliary data structures that scale with the size of the input lists of spells and potions. Temporary variables are used for calculations and comparison, but their number remains constant regardless of the input size. Thus, the auxiliary space complexity is constant.

Optimal Solution

Approach

To efficiently count successful pairs, we'll use a combination of sorting and clever searching. Sorting allows us to quickly find potions that, when paired with a given spell, meet the success threshold without checking every single potion.

Here's how the algorithm would work step-by-step:

First, sort the list of potions from smallest to largest. This will let us use a trick to find the right potions quickly.
Now, for each spell, calculate the minimum strength a potion needs to be successful when combined with that spell.
Use a method to quickly find the first potion in the sorted list that meets or exceeds the minimum required strength. Because the potions are sorted, all potions after this one will also be strong enough.
The number of potions that are strong enough is simply the total number of potions minus the position where the first suitable potion was found.
Repeat this process for each spell, adding up the number of successful potion pairings for each. This total count is your answer.
By sorting the potions and using searching, you avoid multiplying through every possible spell-potion combination. This saves a lot of time.

Code Implementation

def successfulPairs(spells, potions, success):
    number_of_potions = len(potions)
    successful_pairs_count = 0

    potions.sort()

    for current_spell in spells:
        # Determine minimum potion strength needed for success.
        minimum_potion_strength = (success + current_spell - 1) // current_spell

        # Binary search to find the first suitable potion.
        left_index = 0
        right_index = number_of_potions

        while left_index < right_index:
            middle_index = left_index + (right_index - left_index) // 2
            if potions[middle_index] < minimum_potion_strength:
                left_index = middle_index + 1
            else:
                right_index = middle_index

        # Count successful pairs based on the search result.
        successful_pairs_count += number_of_potions - left_index

    return successful_pairs_count

Big(O) Analysis

Time Complexity

O(n log n + m log k) – Sorting the potions array takes O(k log k) time, where k is the number of potions. For each of the m spells, we perform a binary search on the sorted potions array, which takes O(log k) time. Since we iterate through all m spells, the binary search portion takes O(m log k) time. Therefore, the total time complexity is O(k log k + m log k). If we assume the length of spells is represented by n and the length of potions by k, then the sorting is O(k log k) and the binary search part across all spells become O(n log k). Therefore, it becomes O(n log k + k log k). Assuming k > n, we can approximate this as O(n log n + m log k).

Space Complexity

O(1) – The space complexity is primarily determined by the sorting algorithm applied to the potions. Assuming an in-place sorting algorithm like heapsort or quicksort is used, the auxiliary space required for sorting is O(1). The remaining steps involve calculating the minimum strength and finding the first suitable potion, which can be done using a constant amount of extra space for variables such as spell strength, minimum required potion strength, and indices for binary search. Therefore, the overall auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty spells or potions array	Return an empty list of successful pairs, since no pairs can be formed.
spells or potions array containing negative numbers	Handle negative numbers correctly during multiplication and comparison with the success value.
success value is zero	Consider the case where multiplying any spell and potion results in success.
success value is very large (close to maximum integer value)	Be wary of potential integer overflow during multiplication; use long type to avoid it.
spells or potions array containing very large numbers (close to maximum integer value)	Use long to avoid integer overflow when calculating the product of spell and potion values.
All pairs successful (product of all spells and potions >= success)	Ensure the algorithm correctly identifies and counts all successful pairs.
No pairs successful (product of all spells and potions < success)	Algorithm correctly returns 0 for that element of spells.
spells and/or potions arrays are very large, impacting performance.	Sorting the potions array and using binary search provides efficient counting of successful pairs.