Skip to content

2300. Successful Pairs of Spells and Potions 👍

  • Time: $O(\texttt{sort} + O(n\log m)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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]