#2300 - Successful Pairs of Spells and Potions

MediumBinary Search

Given arrays spells and potions, and an integer success, a pair (i, j) is successful if spells[i] * potions[j] >= success. Return an array where each element is the number of successful pairs for that spell.

Input	Output
spells = [5,1,3], potions = [1,2,3,4,5], success = 7	[4,0,3]
spells = [3,1,2], potions = [8,5,8], success = 16	[2,0,2]

Solution Space

Try it

/**
 * For each spell, counts the number of potions forming a successful pair.
 * Sorts potions, then binary-searches for the threshold per spell.
 *
 * @param spells  Array of spell strengths
 * @param potions Array of potion strengths
 * @param success Minimum product threshold
 * @returns       Array of successful pair counts per spell
 */
export function successfulPairs(
  spells: number[],
  potions: number[],
  success: number,
): number[] {
  potions.sort((a, b) => a - b);
  const m = potions.length;

  return spells.map((spell) => {
    // Minimum potion needed: ceil(success / spell)
    const minPotion = Math.ceil(success / spell);

    // Binary search for first potion >= minPotion
    let lo = 0;
    let hi = m;
    while (lo < hi) {
      const mid = lo + Math.floor((hi - lo) / 2);
      if (potions[mid] < minPotion) lo = mid + 1;
      else hi = mid;
    }

    return m - lo; // all potions from lo onwards are successful
  });
}

Approach: sort + binary search – sort potions once, then for each spell binary-search for the smallest potion that meets the threshold.

Time: O(m log m + n log m) – sorting potions is O(m log m); each of n spells does O(log m) search.

Space: O(1) extra – sorting is in-place; output array is required.

#875 Koko Eating Bananas

#17 Letter Combinations of a Phone Number