How do you solve Successful Pairs of Spells and Potions?

Sort potions ascending. For each spell, use binary search to find the smallest index in potions where potion >= ceil(success / spell). The count of successful potions is total potions minus this index. Append this count to the result array. Return the result after processing all spells.

Successful Pairs of Spells and Potions

Q: What is the time complexity of Successful Pairs of Spells and Potions?

O(n log m). Sorting potions takes O(m log m). For each of the n spells, a binary search on potions takes O(log m), resulting in O(n log m) total after sorting.

Q: What pattern does Successful Pairs of Spells and Potions use?

The Pattern: Binary Search (Lower Bound Search in Sorted Array) The Heuristic: When searching for the count of elements meeting a threshold in a sorted array, use binary search to find the first valid element's index, then subtract from the total length to get the count efficiently.

Medium Binary Search

Problem

Given two integer arrays spells and potions, and an integer success, return an array where each element is the number of potions that when multiplied with the corresponding spell produce a product greater than or equal to success.

1 ≤ spells.length, potions.length ≤ 10⁵
1 ≤ spells[i], potions[i] ≤ 10⁵
1 ≤ success ≤ 10¹⁰

Example

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

Output: [4,0,3]

For spell 5, potions that satisfy 5 * potion >= 7 are [2,3,4,5], count = 4. For spell 1, no potion satisfies 1 * potion >= 7, count = 0. For spell 3, potions [3,4,5] satisfy 3 * potion >= 7, count = 3. The algorithm sorts potions to enable binary search. For each spell, it performs a binary search to find the first potion that meets the success threshold, then counts how many potions remain.

Approach

Straightforward Solution

A naive approach would check every pair of spell and potion, resulting in O(n*m) time complexity, which is infeasible for large inputs.

Core Observation

The problem reduces to, for each spell, finding the count of potions where spell * potion >= success. Since potions are positive, this inequality can be rearranged to potion >= ceil(success / spell). This transforms the problem into a search for the lower bound in a sorted array.

Path to Optimal

Preview

Sorting potions allows binary search to find the first potion meeting the threshold for each spell in O(log m) time. This reduces the overall complexity to O(n log m)…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Sort potions ascending. For each spell, use binary search to find the smallest index in potions where potion >= ceil(success / spell)…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n log m)

Sorting potions takes O(m log m). For each of the n spells, a binary search on potions takes O(log m), resulting in O(n log m) total after sorting.

Space

O(m)

Sorting potions is done in-place or with O(m) auxiliary space depending on the sorting algorithm. The result array uses O(n) space, which is required for output.

Pattern Spotlight

Binary Search (Lower Bound Search in Sorted Array)

When searching for the count of elements meeting a threshold in a sorted array, use binary search to find the first valid element's index, then subtract from the total length to get the count efficiently.

Solution

Python

1class Solution:
  def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
      potions.sort()
      result = []
5
      for spell in spells:
          left = 0
          right = len(potions) - 1
          first_successful = len(potions)
10
          while left <= right:
              mid = (left + right) // 2
13
              if spell * potions[mid] >= success:
                  first_successful = mid
                  right = mid - 1
              else:
                  left = mid + 1
19
          result.append(len(potions) - first_successful)
21
      return result

Step-by-Step Solution

Sort Potions to Enable Efficient Threshold Searches

3	`potions.sort()`

Objective

To prepare the potions array for binary search by sorting it in ascending order.

Key Insight

Sorting potions is essential because binary search requires a sorted array to function correctly. This preprocessing step transforms the problem from an O(n*m) brute-force search into a more efficient O(n log m) approach by enabling quick threshold lookups.

Interview Quick-Check

Core Logic

Sorting potions allows binary search to find the first potion meeting the success threshold efficiently.

Complexity

Sorting takes O(m log m) time, which is acceptable given the large input size and the efficiency gains in subsequent searches.

Iterate Over Spells and Use Binary Search to Find Threshold Index

For each spell, perform a binary search on potions to find the smallest index where the product meets or exceeds success.

Calculate and Append the Count of Successful Potions for Each Spell

To compute the number of potions that form successful pairs with the current spell and append this count to the result list.

Return the Final Result Array After Processing All Spells

To return the array containing counts of successful potions for each spell after all computations are complete.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 14 Critical

if spell * potions[mid] >= success:

Check if the product of spell and potion at mid meets or exceeds success.

This comparison is the critical decision point in the binary search, identifying whether to move left or right to find the earliest potion meeting the success threshold.

Full line-by-line criticality + rationale for all 14 lines available on Pro.

Test Your Understanding

Why is binary search the appropriate method to find the count of potions that satisfy the success condition for each spell?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Successful Pairs of Spells and Potions from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Successful Pairs of Spells and Potions drill

or drill a free problem

1	`class Solution:`
2	`def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:`
3	`potions.sort()`
4	`result = []`
5
6	`for spell in spells:`
7	`left = 0`
8	`right = len(potions) - 1`
9	`first_successful = len(potions)`
10
11	`while left <= right:`
12	`mid = (left + right) // 2`
13
14	`if spell * potions[mid] >= success:`
15	`first_successful = mid`
16	`right = mid - 1`
17	`else:`
18	`left = mid + 1`
19
20	`result.append(len(potions) - first_successful)`
21
22	`return result`