# Successful Pairs of Spells and Potions
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/successful-pairs-of-spells-and-potions)
Canonical: https://scaleengineer.com/dsa/problems/successful-pairs-of-spells-and-potions
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs)
---
## Problem
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`

# Approaches
## Brute Force Iteration
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.
**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).
**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).
### Explanation
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.
```java
class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length;
        int m = potions.length;
        int[] pairs = new int[n];
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < m; j++) {
                if ((long) spells[i] * potions[j] >= success) {
                    count++;
                }
            }
            pairs[i] = count;
        }
        return pairs;
    }
}
```
### Algorithm
- 1. Create an integer array `pairs` of size `n`.
- 2. For each `spell` at index `i` in `spells`:
- 3.    Initialize `count = 0`.
- 4.    For each `potion` at index `j` in `potions`:
- 5.        If `(long) spells[i] * potions[j] >= success`, increment `count`.
- 6.    Set `pairs[i] = count`.
- 7. Return `pairs`.

## Sorting Potions with Binary Search
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.
**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.
**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.
### Explanation
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`.
```java
import java.util.Arrays;

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length;
        int m = potions.length;
        int[] pairs = new int[n];
        
        Arrays.sort(potions);
        
        for (int i = 0; i < n; i++) {
            long minPotion = (success + spells[i] - 1) / spells[i];
            
            // Binary search to find the first potion >= minPotion
            int left = 0;
            int right = m - 1;
            int index = m; // Default if no potion is strong enough
            
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if ((long)potions[mid] >= minPotion) {
                    index = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            pairs[i] = m - index;
        }
        
        return pairs;
    }
}
```
### Algorithm
- 1. Sort the `potions` array in ascending order.
- 2. Create an integer array `pairs` of size `n`.
- 3. For each `spell` at index `i` in `spells`:
- 4.    Calculate the minimum required potion strength: `min_potion = (success + spells[i] - 1) / spells[i]`.
- 5.    Perform a binary search on `potions` to find the leftmost index `k` where `potions[k] >= min_potion`.
- 6.    The number of successful pairs is `m - k`. Store this in `pairs[i]`.
- 7. Return `pairs`.

## Sorting Both Arrays with Two Pointers
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.
**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.
**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.
### Explanation
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.
```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length;
        int m = potions.length;
        
        int[][] sortedSpells = new int[n][2];
        for (int i = 0; i < n; i++) {
            sortedSpells[i][0] = spells[i];
            sortedSpells[i][1] = i;
        }
        
        Arrays.sort(sortedSpells, Comparator.comparingInt(a -> a[0]));
        Arrays.sort(potions);
        
        int[] pairs = new int[n];
        int potionIndex = m - 1;
        
        for (int i = 0; i < n; i++) {
            int spell = sortedSpells[i][0];
            int originalIndex = sortedSpells[i][1];
            
            while (potionIndex >= 0 && (long) spell * potions[potionIndex] >= success) {
                potionIndex--;
            }
            
            pairs[originalIndex] = m - 1 - potionIndex;
        }
        
        return pairs;
    }
}
```
### Algorithm
- 1. Create a 2D array `sortedSpells` of size `n x 2` to store `(spell, original_index)`.
- 2. Sort `sortedSpells` based on spell strength.
- 3. Sort the `potions` array.
- 4. Initialize `potionIndex = m - 1` and the result array `pairs`.
- 5. Iterate `i` from `0` to `n-1` through `sortedSpells`.
- 6.    Let `spell = sortedSpells[i][0]` and `originalIndex = sortedSpells[i][1]`.
- 7.    While `potionIndex >= 0` and `(long) spell * potions[potionIndex] >= success`:
- 8.        Decrement `potionIndex`.
- 9.    The count of successful potions is `m - 1 - potionIndex`.
- 10.   Set `pairs[originalIndex]` to this count.
- 11. Return `pairs`.

# Solutions
### Java

```java
class Solution {
public
  int[] successfulPairs(int[] spells, int[] potions, long success) {
    Arrays.sort(potions);
    int n = spells.length, m = potions.length;
    int[] ans = new int[n];
    for (int i = 0; i < n; ++i) {
      int left = 0, right = m;
      while (left < right) {
        int mid = (left + right) >> 1;
        if ((long)spells[i] * potions[mid] >= success) {
          right = mid;
        } else {
          left = mid + 1;
        }
      }
      ans[i] = m - left;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> successfulPairs(vector<int> &spells, vector<int> &potions,
                              long long success) {
    sort(potions.begin(), potions.end());
    vector<int> ans;
    int m = potions.size();
    for (int &v : spells) {
      int i = lower_bound(potions.begin(), potions.end(), success * 1.0 / v) -
              potions.begin();
      ans.push_back(m - i);
    }
    return ans;
  }
};

```

### Python

```python
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]

```