What is the key insight for Successful Pairs of Spells and Potions?

The key insight is that if a spell pairs successfully with a potion, it will also pair successfully with all stronger potions, allowing binary search over sorted potions.

Can we solve this problem without sorting?

Sorting is necessary for efficient binary search. Without sorting, we would need a brute-force O(n*m) approach which is inefficient for large inputs.

How do we calculate the potion threshold for each spell?

For a spell s, the threshold potion strength is ceil(success / s). Potions below this threshold cannot form successful pairs.

Is there an alternative to binary search?

Yes, using two pointers over sorted potions can reduce repeated searches and still leverage the monotonic success property.

What common mistakes should be avoided?

Avoid unsorted potions, miscalculating thresholds with integer division, and attempting brute-force multiplication for all spell-potion pairs.

#2300

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

咒语和药水的成功对数

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度， potions[j] 表示第 j 瓶药水的能量强度。同时给你一个整数 success 。一个咒语和药水的能量强度相乘如果大于等于 success ，那么…

数组双指针二分查找排序

题目描述

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。

同时给你一个整数 success 。一个咒语和药水的能量强度相乘如果 大于等于 success ，那么它们视为一对成功的组合。

请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的药水数目。

示例 1：

输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出：[4,0,3]
解释：
- 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
- 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
- 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
所以返回 [4,0,3] 。

示例 2：

输入：spells = [3,1,2], potions = [8,5,8], success = 16
输出：[2,0,2]
解释：
- 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
- 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
- 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
所以返回 [2,0,2] 。

提示：

n == spells.length
m == potions.length
1 <= n, m <= 10⁵
1 <= spells[i], potions[i] <= 10⁵
1 <= success <= 10¹⁰

lightbulb

解题思路

方法一：排序 + 二分查找

我们可以对药水数组进行排序，然后遍历咒语数组，对于每个咒语 $v$ ，利用二分查找找到第一个大于等于 $\frac{success}{v}$ 的药水，下标记为 $i$ ，那么药水的长度减去 $i$ 即为能跟该咒语成功组合的药水数目。

时间复杂度 $O((m + n) \times \log m)$ ，空间复杂度 $O(\log n)$ 。其中 $m$ 和 $n$ 分别为药水数组和咒语数组的长度。

1

2

3

4

5

6

7

8

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]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expecting recognition of monotonic success property: stronger potions always succeed if weaker ones do.
question_mark
Looking for application of binary search over answer space instead of brute-force multiplication checks.
question_mark
Checking understanding of sorting as a prerequisite to reduce per-spell search time.

warning

常见陷阱

外企场景

error
Failing to sort potions before binary search, leading to incorrect counts.
error
Using integer division incorrectly when computing the required potion threshold.
error
Attempting brute-force O(n*m) approach which is too slow for large arrays.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the list of actual successful potion indices for each spell instead of counts.
arrow_right_alt
Find spells that pair successfully with at least k potions instead of counting all pairs.
arrow_right_alt
Modify for negative numbers where success requires product >= threshold with mixed signs.

help

常见问题

外企场景

继续练习

#2332 坐上公交的最晚时间 #2234 花园的最大总美丽值 #2071 你可以安排的最多任务数目