LeetCode 2300. Successful Pairs of Spells and Potions Solution in Java, C++, Python & More | Explanation + Code

Description

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

Solutions

Solution 1: 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 ^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) × 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.

PythonJavaC++GoTypeScriptRust

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](code-box)

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; } }(code-box)

class Solution { public: vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) { ranges::sort(potions); const int m = potions.size(); vector<int> ans; ans.reserve(spells.size()); for (int v : spells) { auto it = ranges::lower_bound(potions, static_cast<double>(success) / v); ans.push_back(m - static_cast<int>(it - potions.begin())); } return ans; } };(code-box)

func successfulPairs(spells []int, potions []int, success int64) (ans []int) { sort.Ints(potions) m := len(potions) for _, v := range spells { i := sort.Search(m, func(i int) bool { return int64(potions[i]*v) >= success }) ans = append(ans, m-i) } return ans }(code-box)

function successfulPairs(spells: number[], potions: number[], success: number): number[] { potions.sort((a, b) => a - b); const m = potions.length; const ans: number[] = []; for (const v of spells) { const targetPotion = success / v; const idx = _.sortedIndexBy(potions, targetPotion, p => p); ans.push(m - idx); } return ans; }(code-box)

impl Solution { pub fn successful_pairs(spells: Vec<i32>, mut potions: Vec<i32>, success: i64) -> Vec<i32> { potions.sort(); let m = potions.len(); let mut ans = Vec::with_capacity(spells.len()); for &v in &spells { let target = (success + v as i64 - 1) / v as i64; let idx = potions.partition_point(|&p| (p as i64) < target); ans.push((m - idx) as i32); } ans } }(code-box)