Successful pairs of spells and potions

Array Two Pointers Binary Search Sorting

49.5% acceptance

Feb 25, 2026

3196

105

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn successful_pairs(spells: Vec<i32>, mut potions: Vec<i32>, success: i64) -> Vec<i32> {
    potions.sort_unstable();
    let m = potions.len();
    spells.iter().map(|&s| {
      let s = s as i64;
      // need s * p >= success, i.e. p >= ceil(success / s)
      let min_potion = (success + s - 1) / s;
      // binary search for first potion >= min_potion
      let idx = potions.partition_point(|&p| (p as i64) < min_potion);
      (m - idx) as i32
    }).collect()
  }
}