Skip to main content
Talentd

Successful Pairs of Spells and Potions - Solution & Explanation

MediumArrayTwo PointersBinary SearchSorting11 min readAsked at: Amazon, Microsoft, Goldman Sachs +4
Practice this problem

Problem Statement

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.

 

Example 1:

Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation:
- 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]
Explanation:
- 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

Approach Overview

Problem Overview: You are given two arrays: spells and potions. A pair is successful if spells[i] * potions[j] >= success. For each spell, compute how many potions form a successful pair.

Approach 1: Brute Force (O(n * m) time, O(1) space)

The most direct solution checks every possible pair. For each value in spells, iterate through the entire potions array and compute the product. If the product meets or exceeds success, increment the count for that spell. This approach uses two nested loops and performs a multiplication check for every pair.

The implementation is straightforward and useful for validating logic or small inputs. However, it becomes slow when both arrays are large because the algorithm evaluates n * m combinations. With constraints in the tens of thousands, this approach easily times out.

Approach 2: Sorting and Binary Search (O(n log m + m log m) time, O(1) extra space)

A more efficient solution sorts the potions array first. Once sorted, you can determine the minimum potion value needed for a spell to succeed. For a spell value s, the requirement is s * potion >= success, which implies potion >= ceil(success / s). Instead of scanning the entire array, perform a binary search to find the first potion meeting this threshold.

After locating the first valid index, every potion to the right of it will also work because the array is sorted. The count becomes len(potions) - index. Repeat this process for each spell. Sorting is done once, then each spell query runs in logarithmic time.

This approach combines sorting with binary search to avoid redundant comparisons. The idea of converting the inequality into a searchable threshold is the key insight. You never explicitly test every pair.

Recommended for interviews: The sorting + binary search approach is what interviewers expect. The brute force solution shows you understand the pairing requirement, but the optimized version demonstrates familiarity with array preprocessing and logarithmic search techniques. Recognizing that the inequality can be turned into a lower bound search is the core skill being tested.

Approach 1: Approach 1: Brute Force

This approach involves iterating over each spell and checking the product with every potion to see if it exceeds the 'success' threshold. Though simple to understand and implement, this approach is inefficient for large input sizes due to its O(n * m) time complexity.

The function successfulPairs takes three parameters: spells, potions, and success. It iterates over each spell and computes the number of potions that can combine with it to meet the success criterion.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n * m) where n is the number of spells and m is the number of potions.
Space Complexity: O(1) aside from the output list which requires O(n).

Try this approach in the editor →

Approach 2: Approach 2: Sorting and Binary Search

This approach leverages sorting and binary search for optimization. By sorting the potions array, for each spell, we can binary search to find the least potion that meets the success criterion, allowing us to efficiently count the valid potions.

We use Python's built-in bisect_left for binary searching the sorted potions array to find the first valid potion for each spell. The number of successful pairs is calculated by the count of potions at and beyond this index.

Code

PythonC++Java

Python

C++

Java

Complexity

Time Complexity: O(m log m + n log m) due to sorting and binary searches.
Space Complexity: O(1) aside from space for the result list.

Try this approach in the editor →

Approach 3: 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.

The time complexity is O((m + n) times log m), and the space complexity is O(log n). Here, m and n are the lengths of the potion array and the spell array, respectively.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Brute Force

Time Complexity: O(n * m) where n is the number of spells and m is the number of potions.
Space Complexity: O(1) aside from the output list which requires O(n).

Approach 2: Sorting and Binary Search

Time Complexity: O(m log m + n log m) due to sorting and binary searches.
Space Complexity: O(1) aside from space for the result list.

Sorting + Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(n * m)O(1)Small inputs or when first verifying the pairing logic
Sorting + Binary SearchO(m log m + n log m)O(1)Large arrays where efficient lookups are required for each spell

Video Solution

Successful Pairs of Spells and Potions - Leetcode 2300 - Python • NeetCodeIO • 24,860 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Successful Pairs of Spells and Potions easy or hard?
The problem is rated Medium because the brute force idea is simple but inefficient. The challenge is recognizing that the inequality can be converted into a threshold and solved using sorting and binary search. Candidates comfortable with search boundaries and array preprocessing usually solve it quickly.
Successful Pairs of Spells and Potions Python/Java solution
Most implementations first sort the potions array, then loop through each spell and apply binary search to find the minimum potion index satisfying spell * potion >= success. Python commonly uses bisect, while Java and C++ implement lower_bound style binary search. Each spell result is computed in O(log m).
How to solve Successful Pairs of Spells and Potions in O(n)?
An exact O(n) solution is not typical unless the potions array is already sorted and constraints allow linear scanning with two pointers. In the general case, sorting followed by binary search is used. That approach runs in O(m log m + n log m), which is efficient for arrays up to 10^5 elements.
What is the best approach for Successful Pairs of Spells and Potions?
The optimal approach sorts the potions array and then performs a binary search for each spell. For a spell value s, compute the minimum potion value required as ceil(success / s). Binary search finds the first potion meeting that threshold, and all elements to the right are valid pairs. The overall complexity becomes O(m log m + n log m).
Is Successful Pairs of Spells and Potions asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving sorting and binary search on arrays. Variations of threshold search problems appear in interviews at companies like Amazon, Google, and Meta, where candidates must convert a condition into a searchable boundary in a sorted structure.
What data structure is used in Successful Pairs of Spells and Potions?
The core data structures are arrays for storing spells and potions. The optimized solution relies on sorting the potions array and applying binary search to locate the first valid potion for each spell. No additional complex structures like heaps or hash maps are required.
What is the time complexity of Successful Pairs of Spells and Potions?
The brute force approach runs in O(n * m) time because every spell is multiplied with every potion. The optimized solution sorts the potions array in O(m log m) time and performs a binary search for each spell in O(log m). This results in a total complexity of O(m log m + n log m) with constant extra space.

Ready to solve this problem?

Practice Successful Pairs of Spells and Potions with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Subsequence With Limited Sum

Next

Maximum Matching of Players With Trainers