LeetCode 2300 - Successful Pairs of Spells and Potions

The problem asks us to determine, for each spell, how many potions it can pair with to achieve a product of at least success. The arrays spells and potions represent the strengths of spells and potions, respectively.

leetcodemediumarraytwo-pointersbinary-searchsorting

LeetCode Problem 2300

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Binary Search, Sorting

Solution

Problem Understanding

The problem asks us to determine, for each spell, how many potions it can pair with to achieve a product of at least success. The arrays spells and potions represent the strengths of spells and potions, respectively. The output is an array of integers where each element corresponds to the number of successful potion pairings for the respective spell.

In essence, for each spell[i], we need to count the number of potions[j] such that:

spells[i] * potions[j] >= success

The constraints indicate that both spells and potions can have up to 100,000 elements, and strengths can be as large as 100,000, while success can reach 10^10. This means a naive solution that checks all pairs would require up to 10^10 operations in the worst case, which is far too slow.

Key edge cases include very small or very large numbers, cases where no potions satisfy a spell, or where all potions satisfy it. The input guarantees positive integers, so we do not need to handle zero or negative values.

Approaches

Brute Force

The simplest approach is to iterate over every spell and multiply it with every potion, checking if the product is at least success. This guarantees correctness because it explicitly evaluates the condition for all possible pairs. However, the time complexity is O(n * m), which can be up to 10^10 operations for the maximum constraints, making it impractical.

Optimal Approach

The key insight is that for a fixed spell s, the condition s * p >= success can be rewritten as p >= ceil(success / s). This means we only need to count the number of potions greater than or equal to success / s. If we sort potions first, we can use binary search to efficiently find this count.

The algorithm proceeds as follows:

  1. Sort the potions array.
  2. For each spell s, compute the minimum required potion strength min_potion = ceil(success / s).
  3. Use binary search to find the first potion that meets or exceeds min_potion.
  4. The number of successful pairs for that spell is the total potions minus the index found.

This reduces the time complexity significantly, as sorting is O(m log m) and each spell takes O(log m) for the binary search, leading to an overall complexity of O(m log m + n log m).

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(1) Checks all pairs explicitly
Optimal O(m log m + n log m) O(1) Sort potions and use binary search for each spell

Algorithm Walkthrough

  1. Sort the potions array in ascending order. Sorting allows us to efficiently find the threshold potion using binary search.
  2. Initialize an empty result array pairs to store the count for each spell.
  3. Iterate through each spell in spells:

a. Compute min_potion = ceil(success / spell). This is the minimum strength a potion must have to form a successful pair.

b. Perform a binary search on the sorted potions array to find the index of the first potion >= min_potion.

c. Compute the number of successful pairs as len(potions) - index_found.

d. Append this count to pairs. 4. Return the pairs array.

Why it works: Sorting ensures that all potions beyond the binary search index satisfy the success condition. Binary search guarantees we find the smallest such potion efficiently. Therefore, the algorithm correctly counts all successful pairs for each spell.

Python Solution

from typing import List
import bisect
import math

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()
        n = len(potions)
        pairs = []
        
        for spell in spells:
            min_potion = (success + spell - 1) // spell  # ceil division
            idx = bisect.bisect_left(potions, min_potion)
            pairs.append(n - idx)
        
        return pairs

This implementation first sorts the potions array to enable binary search. For each spell, we compute the minimum potion strength required using ceiling division to handle integer math precisely. The bisect_left function finds the first potion that meets this requirement, and subtracting its index from the total number of potions gives the count of successful pairs.

Go Solution

import (
    "sort"
)

func successfulPairs(spells []int, potions []int, success int64) []int {
    sort.Slice(potions, func(i, j int) bool { return potions[i] < potions[j] })
    n := len(potions)
    pairs := make([]int, len(spells))
    
    for i, spell := range spells {
        minPotion := (success + int64(spell) - 1) / int64(spell)
        left, right := 0, n
        for left < right {
            mid := (left + right) / 2
            if int64(potions[mid]) >= minPotion {
                right = mid
            } else {
                left = mid + 1
            }
        }
        pairs[i] = n - left
    }
    
    return pairs
}

In Go, we sort potions using sort.Slice. Integer division requires casting to int64 to prevent overflow. Binary search is implemented manually to find the first potion that meets the requirement. The result array stores the number of successful pairs for each spell.

Worked Examples

Example 1: spells = [5,1,3], potions = [1,2,3,4,5], success = 7

After sorting potions: [1,2,3,4,5]

Spell min_potion idx found successful pairs
5 ceil(7/5)=2 1 5-1=4
1 ceil(7/1)=7 5 5-5=0
3 ceil(7/3)=3 2 5-2=3

Output: [4,0,3]

Example 2: spells = [3,1,2], potions = [8,5,8], success = 16

Sorted potions: [5,8,8]

Spell min_potion idx found successful pairs
3 ceil(16/3)=6 1 3-1=2
1 ceil(16/1)=16 3 3-3=0
2 ceil(16/2)=8 1 3-1=2

Output: [2,0,2]

Complexity Analysis

Measure Complexity Explanation
Time O(m log m + n log m) Sorting potions takes O(m log m), binary search per spell is O(log m), total n spells
Space O(1) No extra space proportional to input, only the output array

The complexity is efficient enough for the input constraints, as n and m are up to 10^5.

Test Cases

# Provided examples
assert Solution().successfulPairs([5,1,3], [1,2,3,4,5], 7) == [4,0,3]  # Example 1
assert Solution().successfulPairs([3,1,2], [8,5,8], 16) == [2,0,2]   # Example 2

# Edge cases
assert Solution().successfulPairs([1], [1], 1) == [1]                 # smallest input
assert Solution().successfulPairs([100000], [100000], 10000000000) == [1]  # largest numbers
assert Solution().successfulPairs([2,3], [1,1,1], 10) == [0,0]       # no successful pairs
assert Solution().successfulPairs([2,3], [10,20,30], 5) == [3,3]     # all successful pairs
assert Solution().successfulPairs([1,2,3], [4,5,6], 12) == [0,0,3]   # mixed case
Test Why
[5,1,3], [1,2,3,4,5], 7 Verifies general case with mixed results
[3,1,2], [8,5,8], 16 Checks repeated potion values
[1], [1], 1 Minimal input boundary
[100000], [100000], 10^10 Max value boundary
[2,3], [1,1,1], 10 Case with no successful pairs
[2,3], [10,20,30], 5 Case with all successful pairs
[1,2,3], [4,5,6], 12 Mixed outcomes for different spells