Problem Description

You have two arrays of positive integers: spells and potions. The spells array has length n and represents the strength of each spell. The potions array has length m and represents the strength of each potion.

You need to determine how many potions can form a successful pair with each spell. A spell and potion form a successful pair when their product (spell strength × potion strength) is at least equal to a given integer value called success.

For each spell in the spells array, you need to count how many potions from the potions array can be paired with it successfully. Return an array pairs of length n, where pairs[i] represents the number of potions that form a successful pair with the i-th spell.

For example, if a spell has strength 5 and success is 20, then any potion with strength 4 or greater would form a successful pair (since 5 × 4 = 20, which meets the threshold).

The solution approach sorts the potions array first, then for each spell v, uses binary search to find the smallest potion that satisfies potion × v ≥ success, which is equivalent to finding potion ≥ success/v. The count of valid potions is the total number of potions minus the index where this threshold is met.

Intuition

The key insight is that for a given spell with strength v, we need to find all potions with strength p such that v × p ≥ success. This can be rearranged to p ≥ success/v.

Once we recognize this inequality, we realize that if we sort the potions array, all valid potions will form a contiguous segment at the end of the sorted array. Why? Because if a potion with strength p works with a spell, then any potion with strength greater than p will also work.

This observation leads us to binary search. For each spell, we don't need to check every potion individually. Instead, we can:

1. Sort the potions array once
2. For each spell, find the minimum potion strength needed: success/v
3. Use binary search to locate where this threshold value would fit in the sorted potions array
4. All potions from this position to the end of the array are valid pairs

The beauty of this approach is that sorting costs O(m log m) once, and then each spell only requires O(log m) time for binary search, giving us a total time complexity of O(m log m + n log m). This is much more efficient than the naive approach of checking every spell-potion pair, which would take O(n × m) time.

The bisect_left function finds the leftmost position where we could insert success/v to keep the array sorted. This gives us the index of the first potion that meets our requirement. Subtracting this index from the total length gives us the count of valid potions.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Solution Approach

The implementation follows a sorting and binary search strategy:

Step 1: Sort the potions array

potions.sort()

We sort the potions array in ascending order. This preprocessing step enables us to use binary search efficiently.

Step 2: Store the length of potions array

m = len(potions)

We store the total number of potions for later calculations.

Step 3: Process each spell using binary search

return [m - bisect_left(potions, success / v) for v in spells]

For each spell v in the spells array:

• Calculate the minimum potion strength needed: success / v
• Use bisect_left(potions, success / v) to find the leftmost insertion point for this value in the sorted potions array
• This gives us the index i where the first valid potion would be located
• The number of valid potions is m - i (all potions from index i to the end)

Why bisect_left? The bisect_left function performs binary search to find the leftmost position where success / v could be inserted while maintaining sorted order. This position represents:

• The index of the first potion with strength ≥ success / v
• All potions from this index onwards will form successful pairs with the current spell

Example walkthrough: If potions = [1, 2, 3, 4, 5], success = 7, and current spell strength is 2:

• Minimum potion needed: 7 / 2 = 3.5
• bisect_left([1, 2, 3, 4, 5], 3.5) returns 3 (index where 3.5 would go)
• Valid potions are at indices 3 and 4 (values 4 and 5)
• Count of valid potions: 5 - 3 = 2

The list comprehension builds the result array by applying this process to each spell, creating an array where each element represents the count of successful pairs for the corresponding spell.

Example Walkthrough

Let's walk through a concrete example to understand the solution approach:

Given:

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

Step 1: Sort the potions array

• potions = [5, 8, 8] (sorted in ascending order)
• m = 3 (length of potions)

Step 2: Process each spell using binary search

For spell[0] = 3:

• We need: 3 × potion ≥ 16
• Minimum potion strength needed: 16 / 3 = 5.33...
• Use bisect_left([5, 8, 8], 5.33) to find where 5.33 would be inserted
• Binary search finds index 1 (5.33 would go after the 5 at index 0)
• Valid potions are at indices 1 and 2 (values 8 and 8)
• Count: 3 - 1 = 2 successful pairs

For spell[1] = 1:

• We need: 1 × potion ≥ 16
• Minimum potion strength needed: 16 / 1 = 16
• Use bisect_left([5, 8, 8], 16) to find where 16 would be inserted
• Binary search finds index 3 (16 would go at the end)
• No potions meet this threshold
• Count: 3 - 3 = 0 successful pairs

For spell[2] = 2:

• We need: 2 × potion ≥ 16
• Minimum potion strength needed: 16 / 2 = 8
• Use bisect_left([5, 8, 8], 8) to find where 8 would be inserted
• Binary search finds index 1 (the leftmost position of value 8)
• Valid potions are at indices 1 and 2 (values 8 and 8)
• Count: 3 - 1 = 2 successful pairs

Final Result: [2, 0, 2]

This example demonstrates how sorting the potions array once allows us to efficiently find the count of valid pairs for each spell using binary search, avoiding the need to check every spell-potion combination individually.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m log m + n log m) which simplifies to O((m + n) × log m)

• Sorting the potions array takes O(m log m) time, where m is the length of the potions array
• For each spell in the spells array, we perform a binary search using bisect_left on the sorted potions array, which takes O(log m) time per spell
• Since we have n spells, the total time for all binary searches is O(n log m)
• Overall time complexity: O(m log m + n log m) = O((m + n) × log m)

Space Complexity: O(log m)

• The sorting operation on the potions array uses O(log m) space for the recursion stack in Python's Timsort algorithm
• The list comprehension creates a new list of size n, but this is the output and typically not counted in space complexity analysis
• The binary search operation bisect_left uses O(1) additional space
• Overall auxiliary space complexity: O(log m)

Note: The reference answer states O(log n) for space complexity, but based on the code analysis, it should be O(log m) since the sorting is performed on the potions array of length m, not the spells array of length n.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Division vs Float Division

The Pitfall: Using integer division (//) instead of float division (/) when calculating the minimum potion strength.

# WRONG - This will truncate the result
min_potion_strength = success // spell_strength  

# CORRECT - Preserves decimal values
min_potion_strength = success / spell_strength

Why it matters: If success = 7 and spell_strength = 2, we need potions with strength ≥ 3.5. Using integer division would give us 3, incorrectly including potions with strength 3 (since 2 × 3 = 6 < 7).

2. Using bisect_right Instead of bisect_left

The Pitfall: Confusing bisect_right with bisect_left, which would give incorrect counts when exact matches exist.

# WRONG - May miss valid potions when exact threshold exists
insert_position = bisect_right(potions, min_potion_strength)

# CORRECT - Finds the leftmost valid position
insert_position = bisect_left(potions, min_potion_strength)

Example: If potions = [1, 2, 4, 4, 5] and we need min_potion_strength = 4:

• bisect_left returns index 2 (first occurrence of 4)
• bisect_right returns index 4 (after last occurrence of 4)
• Using bisect_right would incorrectly exclude the two potions with strength 4

3. Forgetting to Sort the Potions Array

The Pitfall: Applying binary search on an unsorted array, leading to incorrect results.

# WRONG - Binary search requires sorted array
result = [m - bisect_left(potions, success / v) for v in spells]

# CORRECT - Sort first, then apply binary search
potions.sort()
result = [m - bisect_left(potions, success / v) for v in spells]

4. Modifying Original Potions Array

The Pitfall: Sorting the original potions array in-place might be problematic if the original order needs to be preserved elsewhere.

Solution: Create a copy if needed:

sorted_potions = sorted(potions)  # Creates a new sorted list
# OR
sorted_potions = potions.copy()
sorted_potions.sort()

5. Edge Case: Very Small Spell Strength

The Pitfall: When spell strength approaches zero, success / spell_strength can become very large or cause floating-point precision issues.

Solution: While the problem states all values are positive integers, it's good practice to handle edge cases:

for spell_strength in spells:
    if spell_strength == 0:  # Though problem guarantees positive integers
        result.append(0)
        continue
    min_potion_strength = success / spell_strength
    # ... rest of the logic