2300. Successful Pairs of Spells and Potions LeetCode Solution

In this guide, you will get 2300. Successful Pairs of Spells and Potions LeetCode Solution with the best time and space complexity. The solution to Successful Pairs of Spells and Potions problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Successful Pairs of Spells and Potions solution in C++
4. Successful Pairs of Spells and Potions solution in Java
5. Successful Pairs of Spells and Potions solution in Python
6. Additional Resources

Problem Statement of Successful Pairs of Spells and Potions

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

Complexity Analysis

• Time Complexity: O(\texttt{sort} + O(n\log m)
• Space Complexity: O(n)

2300. Successful Pairs of Spells and Potions LeetCode Solution in C++

class Solution {
 public:
  vector<int> successfulPairs(vector<int>& spells, vector<int>& potions,
                              long long success) {
    vector<int> ans;
    ranges::sort(potions);

    for (const int spell : spells)
      ans.push_back(potions.size() -
                    firstIndexSuccess(spell, potions, success));

    return ans;
  }

 private:
  // Returns the first index i s.t. spell * potions[i] >= success.
  int firstIndexSuccess(int spell, const vector<int>& potions, long success) {
    int l = 0;
    int r = potions.size();
    while (l < r) {
      const int m = (l + r) / 2;
      if (static_cast<long>(spell) * potions[m] >= success)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
};
/* code provided by PROGIEZ */

2300. Successful Pairs of Spells and Potions LeetCode Solution in Java

class Solution {
  public int[] successfulPairs(int[] spells, int[] potions, long success) {
    int[] ans = new int[spells.length];
    Arrays.sort(potions);

    for (int i = 0; i < spells.length; ++i)
      ans[i] = potions.length - firstIndexSuccess(spells[i], potions, success);

    return ans;
  }

  // Returns the first index i s.t. spell * potions[i] >= success.
  private int firstIndexSuccess(int spell, int[] potions, long success) {
    int l = 0;
    int r = potions.length;
    while (l < r) {
      final int m = (l + r) / 2;
      if ((long) spell * potions[m] >= success)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}
// code provided by PROGIEZ

2300. Successful Pairs of Spells and Potions LeetCode Solution in Python

class Solution:
  def successfulPairs(
      self,
      spells: list[int],
      potions: list[int],
      success: int,
  ) -> list[int]:
    potions.sort()

    def firstIndexSuccess(spell: int):
      """Returns the first index i s.t. spell * potions[i] >= success."""
      l = 0
      r = len(potions)
      while l < r:
        m = (l + r) // 2
        if spell * potions[m] >= success:
          r = m
        else:
          l = m + 1
      return l

    return [len(potions) - firstIndexSuccess(spell) for spell in spells]
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.