Successful Pairs of Spells and Potions Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

1
2
3
4
5
6
7
8
9

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.

Solution

Question reduces to finding no of potions for each spell which have product greater than success where product is (each spell * potions[i]). Now decision is whether to keep the potions array sorted or not.

Method 1 – Brute Force

Intuition

The most straightforward approach is to check every possible pair of spell and potion. For each spell, we iterate through all potions and count how many pairs have a product greater than or equal to the given success threshold. This method does not require sorting and works directly with the input arrays.

Approach

  1. For each spell in the spells array:
    • Loop through every potion in the potions array.
    • Multiply the spell and potion values.
    • If the product is greater than or equal to success, increment the count for that spell.
  2. Store the count for each spell in the result array.
  3. Return the result array after processing all spells.

Complexity

  • ⏰ Time complexity: O(n * m), where n is the number of spells and m is the number of potions. We check every possible pair.
  • 🧺 Space complexity: O(n), for the result array storing the count for each spell.

Method 2 – Sort Potions and Use Binary Search

Intuition

To improve efficiency, we sort the potions array. For each spell, we want to count how many potions can form a successful pair (i.e., spell * potion >= success). Since the potions are sorted, we can use binary search to quickly find the first potion that meets the threshold for each spell.

Approach

  1. Sort the potions array in non-decreasing order.
  2. For each spell:
    • Use binary search to find the smallest index i such that spell * potions[i] >= success.
    • The number of successful pairs for this spell is potions.length - i.
  3. Store the result for each spell in the answer array.
  4. Return the answer array.

This approach leverages the sorted order of potions to reduce the search for each spell from linear to logarithmic time.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
	vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
		sort(potions.begin(), potions.end());
		int m = potions.size();
		vector<int> res;
		for (int spell : spells) {
			int left = 0, right = m;
			while (left < right) {
				int mid = left + (right - left) / 2;
				if ((long long)spell * potions[mid] < success) left = mid + 1;
				else right = mid;
			}
			res.push_back(m - left);
		}
		return res;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

import (
	"sort"
)
func successfulPairs(spells []int, potions []int, success int64) []int {
	sort.Ints(potions)
	m := len(potions)
	res := make([]int, len(spells))
	for i, spell := range spells {
		left, right := 0, m
		for left < right {
			mid := left + (right-left)/2
			if int64(spell)*int64(potions[mid]) < success {
				left = mid + 1
			} else {
				right = mid
			}
		}
		res[i] = m - left
	}
	return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

import java.util.*;
class Solution {
	public int[] successfulPairs(int[] spells, int[] potions, long success) {
		Arrays.sort(potions);
		int m = potions.length;
		int[] res = new int[spells.length];
		for (int i = 0; i < spells.length; i++) {
			int left = 0, right = m;
			while (left < right) {
				int mid = left + (right - left) / 2;
				if ((long)spells[i] * potions[mid] < success) left = mid + 1;
				else right = mid;
			}
			res[i] = m - left;
		}
		return res;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
	fun successfulPairs(spells: IntArray, potions: IntArray, success: Long): IntArray {
		potions.sort()
		val m = potions.size
		return spells.map { spell ->
			var left = 0
			var right = m
			while (left < right) {
				val mid = left + (right - left) / 2
				if (spell.toLong() * potions[mid] < success) left = mid + 1
				else right = mid
			}
			m - left
		}.toIntArray()
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

from bisect import bisect_left
class Solution:
	def successfulPairs(self, spells: list[int], potions: list[int], success: int) -> list[int]:
		potions.sort()
		m = len(potions)
		res = []
		for spell in spells:
			# Find the smallest index where spell * potion >= success
			left, right = 0, m
			while left < right:
				mid = (left + right) // 2
				if spell * potions[mid] < success:
					left = mid + 1
				else:
					right = mid
			res.append(m - left)
		return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
	pub fn successful_pairs(spells: Vec<i32>, mut potions: Vec<i32>, success: i64) -> Vec<i32> {
		potions.sort();
		let m = potions.len();
		spells.iter().map(|&spell| {
			let (mut left, mut right) = (0, m);
			while left < right {
				let mid = left + (right - left) / 2;
				if (spell as i64) * (potions[mid] as i64) < success {
					left = mid + 1;
				} else {
					right = mid;
				}
			}
			(m - left) as i32
		}).collect()
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

function successfulPairs(spells: number[], potions: number[], success: number): number[] {
	potions.sort((a, b) => a - b);
	const m = potions.length;
	return spells.map(spell => {
		let left = 0, right = m;
		while (left < right) {
			const mid = Math.floor(left + (right - left) / 2);
			if (spell * potions[mid] < success) left = mid + 1;
			else right = mid;
		}
		return m - left;
	});
}

Complexity

  • ⏰ Time complexity: O(n log m), where n is the number of spells and m is the number of potions. Sorting potions takes O(m log m), and for each spell, binary search takes O(log m).
  • 🧺 Space complexity: O(n), for the result array storing the count for each spell.