Successful Pairs of Spells and Potions

Med

#2096Time: O(n log n + m log m). O(n log n) for sorting spells, O(m log m) for sorting potions. The two-pointer scan takes O(n + m). The dominant part is the sorting.Space: O(n) to store the `(spell, index)` pairs and the result array.1 company

Patterns

Two Pointers

Algorithms

Binary Search Sorting

Data structures

Array

Companies

Goldman Sachs

Prompt

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the i^th spell and potions[j] represents the strength of the j^th 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 i^th 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 <= 10⁵
1 <= spells[i], potions[i] <= 10⁵
1 <= success <= 10¹⁰

Approaches

3 approaches with complexity analysis and trade-offs.

This is a highly optimized approach that involves sorting both the spells and potions arrays and then using a two-pointer technique to find the counts efficiently. By processing spells in increasing order of strength, we can avoid re-scanning the potions array for each spell.

Algorithm

1. Create a 2D array sortedSpells of size n x 2 to store (spell, original_index).
1. Sort sortedSpells based on spell strength.
1. Sort the potions array.
1. Initialize potionIndex = m - 1 and the result array pairs.
1. Iterate i from 0 to n-1 through sortedSpells.
1. Let spell = sortedSpells[i][0] and originalIndex = sortedSpells[i][1].
1. While potionIndex >= 0 and (long) spell * potions[potionIndex] >= success:
1. Decrement `potionIndex`.
1. The count of successful potions is m - 1 - potionIndex.
1. Set pairs[originalIndex] to this count.
1. Return pairs.

Walkthrough

The main challenge with sorting spells is that the final result must correspond to the original order of spells. To handle this, we create a 2D array to store each spell's value along with its original index. First, we populate this new structure with (spells[i], i). We then sort this array based on the spell strength and also sort the potions array. We initialize two pointers: one for the sorted spells (say i, from 0 to n-1) and one for the potions array (say j, from m-1 down to 0). We iterate through the sorted spells. The key insight is that as we move to a stronger spell, the required potion strength decreases. Therefore, the j pointer only needs to move from right to left across the potions array and never needs to be reset. For each spell, we move the j pointer to the left (j--) as long as the product is successful. After the inner loop, j points to the strongest potion that is not successful. The number of successful potions is m - 1 - j. We store this count in the result array at the spell's original index, which we saved earlier. Because the j pointer traverses the potions array at most once, the scanning part is very efficient.

1import java.util.Arrays;2import java.util.Comparator;3 4class Solution {5    public int[] successfulPairs(int[] spells, int[] potions, long success) {6        int n = spells.length;7        int m = potions.length;8        9        int[][] sortedSpells = new int[n][2];10        for (int i = 0; i < n; i++) {11            sortedSpells[i][0] = spells[i];12            sortedSpells[i][1] = i;13        }14        15        Arrays.sort(sortedSpells, Comparator.comparingInt(a -> a[0]));16        Arrays.sort(potions);17        18        int[] pairs = new int[n];19        int potionIndex = m - 1;20        21        for (int i = 0; i < n; i++) {22            int spell = sortedSpells[i][0];23            int originalIndex = sortedSpells[i][1];24            25            while (potionIndex >= 0 && (long) spell * potions[potionIndex] >= success) {26                potionIndex--;27            }28            29            pairs[originalIndex] = m - 1 - potionIndex;30        }31        32        return pairs;33    }34}

Complexity

Time

O(n log n + m log m). O(n log n) for sorting spells, O(m log m) for sorting potions. The two-pointer scan takes O(n + m). The dominant part is the sorting.

Space

O(n) to store the `(spell, index)` pairs and the result array.

Trade-offs

Pros

Generally the most efficient approach, especially when n and m are of similar magnitude.
The two-pointer scan is very fast in practice due to linear memory access and fewer complex operations per step compared to binary search.

Cons

Requires extra space to store spell-index pairs.
The logic is the most complex of the three approaches.

A simple, straightforward approach that directly translates the problem statement into code. It iterates through each spell and, for each spell, iterates through all potions to check if their product meets the success threshold.

Algorithm

1. Create an integer array pairs of size n.
1. For each spell at index i in spells:
1. Initialize count = 0.
1. For each potion at index j in potions:
1. If `(long) spells[i] * potions[j] >= success`, increment `count`.
1. Set pairs[i] = count.
1. Return pairs.

Walkthrough

We initialize an answer array pairs of the same size as spells. We loop through each spell in the spells array using an index i. Inside this loop, we start a counter for successful pairs for the current spell. We then start a nested loop to iterate through every potion in the potions array. In the inner loop, we calculate the product of the current spell and potion. It's important to use a long data type for the product to prevent potential integer overflow, as success can be up to 10^10. If the product is greater than or equal to success, we increment the counter. After the inner loop finishes, we store the final count in pairs[i]. This process is repeated for all spells.

1class Solution {2    public int[] successfulPairs(int[] spells, int[] potions, long success) {3        int n = spells.length;4        int m = potions.length;5        int[] pairs = new int[n];6        for (int i = 0; i < n; i++) {7            int count = 0;8            for (int j = 0; j < m; j++) {9                if ((long) spells[i] * potions[j] >= success) {10                    count++;11                }12            }13            pairs[i] = count;14        }15        return pairs;16    }17}

Complexity

Time

O(n * m), where `n` is the length of `spells` and `m` is the length of `potions`. The nested loops lead to a quadratic time complexity.

Space

O(n) to store the result array `pairs`. If the output array is not considered, the space complexity is O(1).

Trade-offs

Pros

Very simple to understand and implement.
Requires no modification of the input arrays.

Cons

Highly inefficient and will result in a 'Time Limit Exceeded' error for large inputs as specified in the constraints (n, m <= 10^5).

This approach optimizes the search for successful potions. Instead of linearly scanning the potions array for each spell, we first sort the potions array. Then, for each spell, we can efficiently find the number of successful potions using binary search.

Algorithm

1. Sort the potions array in ascending order.
1. Create an integer array pairs of size n.
1. For each spell at index i in spells:
1. Calculate the minimum required potion strength: min_potion = (success + spells[i] - 1) / spells[i].
1. Perform a binary search on potions to find the leftmost index k where potions[k] >= min_potion.
1. The number of successful pairs is m - k. Store this in pairs[i].
1. Return pairs.

Walkthrough

The core idea is that for a given spell, if a certain potion is strong enough to form a successful pair, any potion stronger than it will also be successful. This property allows us to use binary search on a sorted potions array. First, we sort the potions array in non-decreasing order. Then, we iterate through each spell in the spells array. For each spell, we need to find the minimum potion strength required to meet the success threshold. This minimum strength is ceil(success / spell). In integer arithmetic, this can be calculated as (success + spell - 1) / spell to avoid floating-point issues. We then perform a binary search on the sorted potions array to find the index of the first potion whose strength is greater than or equal to this minimum required strength. Let's say the binary search returns an index k. This means potions[k] is the weakest potion that works with the current spell. Since the array is sorted, all potions from index k to m-1 will also work. The total number of successful potions is therefore m - k. We store this count in our result array for the current spell. If no potion is strong enough, the binary search will effectively point to an index m, resulting in a count of m - m = 0.

1import java.util.Arrays;2 3class Solution {4    public int[] successfulPairs(int[] spells, int[] potions, long success) {5        int n = spells.length;6        int m = potions.length;7        int[] pairs = new int[n];8        9        Arrays.sort(potions);10        11        for (int i = 0; i < n; i++) {12            long minPotion = (success + spells[i] - 1) / spells[i];13            14            // Binary search to find the first potion >= minPotion15            int left = 0;16            int right = m - 1;17            int index = m; // Default if no potion is strong enough18            19            while (left <= right) {20                int mid = left + (right - left) / 2;21                if ((long)potions[mid] >= minPotion) {22                    index = mid;23                    right = mid - 1;24                } else {25                    left = mid + 1;26                }27            }28            pairs[i] = m - index;29        }30        31        return pairs;32    }33}

Complexity

Time

O(m log m + n log m). Sorting `potions` takes O(m log m). Then, for each of the `n` spells, we perform a binary search on `potions`, which takes O(log m).

Space

O(m) or O(log m) for sorting, depending on the implementation, plus O(n) for the output array.

Trade-offs

Pros

Significantly more efficient than the brute-force approach.
Passes the given constraints.

Cons

Requires modifying the potions array by sorting it.
The logic is more complex than brute force.

Solutions

Solution

1class Solution {2public3  int[] successfulPairs(int[] spells, int[] potions, long success) {4    Arrays.sort(potions);5    int n = spells.length, m = potions.length;6    int[] ans = new int[n];7    for (int i = 0; i < n; ++i) {8      int left = 0, right = m;9      while (left < right) {10        int mid = (left + right) >> 1;11        if ((long)spells[i] * potions[mid] >= success) {12          right = mid;13        } else {14          left = mid + 1;15        }16      }17      ans[i] = m - left;18    }19    return ans;20  }21}

1class Solution {2public:3  vector<int> successfulPairs(vector<int> &spells, vector<int> &potions,4                              long long success) {5    sort(potions.begin(), potions.end());6    vector<int> ans;7    int m = potions.size();8    for (int &v : spells) {9      int i = lower_bound(potions.begin(), potions.end(), success * 1.0 / v) -10              potions.begin();11      ans.push_back(m - i);12    }13    return ans;14  }15};

1class Solution:2    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]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int[] successfulPairs(int[] spells, int[] potions, long success) {4    Arrays.sort(potions);5    int n = spells.length, m = potions.length;6    int[] ans = new int[n];7    for (int i = 0; i < n; ++i) {8      int left = 0, right = m;9      while (left < right) {10        int mid = (left + right) >> 1;11        if ((long)spells[i] * potions[mid] >= success) {12          right = mid;13        } else {14          left = mid + 1;15        }16      }17      ans[i] = m - left;18    }19    return ans;20  }21}

1class Solution {2public:3  vector<int> successfulPairs(vector<int> &spells, vector<int> &potions,4                              long long success) {5    sort(potions.begin(), potions.end());6    vector<int> ans;7    int m = potions.size();8    for (int &v : spells) {9      int i = lower_bound(potions.begin(), potions.end(), success * 1.0 / v) -10              potions.begin();11      ans.push_back(m - i);12    }13    return ans;14  }15};

1class Solution:2    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]

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.