#2300

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Successful Pairs of Spells and Potions

Count how many potions pair successfully with each spell using binary search over sorted potion strengths efficiently.

array two pointers binary search sorting

Problem Statement

You are given two arrays of positive integers, spells and potions. Each element in spells represents a spell's strength, and each element in potions represents a potion's strength. A spell and potion pair is successful if their product is greater than or equal to a given integer success.

Return an array where the ith element is the number of potions that will form a successful pair with the ith spell. Implement an efficient method leveraging the pattern that stronger potions always succeed with a spell if a weaker one does.

Examples

Example 1

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

Output: [4,0,3]

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

Example 2

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

Output: [2,0,2]

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

Constraints

n == spells.length
m == potions.length
1 <= n, m <= 105
1 <= spells[i], potions[i] <= 105
1 <= success <= 1010

Solution Approach

Sort Potions and Apply Binary Search

Sort the potions array in ascending order. For each spell, calculate the minimum potion strength needed to reach success. Use binary search to find the first potion meeting this threshold. Count all potions from that index to the end as successful pairs.

Compute Threshold for Each Spell

For a spell s, the threshold potion strength is ceil(success / s). This ensures that multiplying any potion below the threshold with the spell cannot succeed. Precompute this threshold for each spell to minimize redundant calculations.

Optimize with Two Pointers Alternative

As an alternative, iterate spells in order and maintain a pointer in the sorted potions array. Move the pointer until the potion is strong enough to form a successful pair. This uses the same success monotonicity property and reduces repeated binary searches for similar spell strengths.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting potions takes O(m log m). For each spell, binary search is O(log m), resulting in total O(n log m) time. Space is O(1) extra beyond the output array, since sorting can be in-place.

What Interviewers Usually Probe

Expecting recognition of monotonic success property: stronger potions always succeed if weaker ones do.
Looking for application of binary search over answer space instead of brute-force multiplication checks.
Checking understanding of sorting as a prerequisite to reduce per-spell search time.

Common Pitfalls or Variants

Common pitfalls

Failing to sort potions before binary search, leading to incorrect counts.
Using integer division incorrectly when computing the required potion threshold.
Attempting brute-force O(n*m) approach which is too slow for large arrays.

Follow-up variants

Return the list of actual successful potion indices for each spell instead of counts.
Find spells that pair successfully with at least k potions instead of counting all pairs.
Modify for negative numbers where success requires product >= threshold with mixed signs.

FAQ

What is the key insight for Successful Pairs of Spells and Potions?

The key insight is that if a spell pairs successfully with a potion, it will also pair successfully with all stronger potions, allowing binary search over sorted potions.

Can we solve this problem without sorting?

Sorting is necessary for efficient binary search. Without sorting, we would need a brute-force O(n*m) approach which is inefficient for large inputs.

How do we calculate the potion threshold for each spell?

For a spell s, the threshold potion strength is ceil(success / s). Potions below this threshold cannot form successful pairs.

Is there an alternative to binary search?

Yes, using two pointers over sorted potions can reduce repeated searches and still leverage the monotonic success property.

What common mistakes should be avoided?

Avoid unsorted potions, miscalculating thresholds with integer division, and attempting brute-force multiplication for all spell-potion pairs.

terminal

Solution

Solution 1: Sorting + Binary Search

We can sort the potion array, then traverse the spell array. For each spell $v$, we use binary search to find the first potion that is greater than or equal to $\frac{success}{v}$. We mark its index as $i$. The length of the potion array minus $i$ is the number of potions that can successfully combine with this spell.

1

2

3

4

5

6

7

class Solution:
    def successfulPairs(
        self, spells: List[int], potions: List[int], success: int
    ) -> List[int]:
        potions.sort()
        m = len(potions)
        return [m - bisect_left(potions, success / v) for v in spells]

Continue Practicing

#2332 the latest time to catch a bus #2234 maximum total beauty of the gardens #2071 maximum number of tasks you can assign