Successful Pairs of Spells and Potions: Sort and Binary Search

You have two lists of positive integers, spells (length n) and potions (length m), and a positive integer success. A spell of strength s and a potion of strength p form a successful pair if s × p ≥ success.

Return a list of length n whose i-th entry is the number of potions that form a successful pair with spells[i].

Examples

Input	Output	Why
`spells = [5, 1, 3], potions = [1, 2, 3, 4, 5], success = 7`	`[4, 0, 3]`	5 pairs with 2, 3, 4 and 5; 1 pairs with none; 3 pairs with 3, 4 and 5.
`spells = [3, 1, 2], potions = [8, 5, 8], success = 16`	`[2, 0, 2]`

Constraints

1 ≤ n, m ≤ 10⁵
1 ≤ spells[i], potions[j] ≤ 10⁵
1 ≤ success ≤ 10⁹ (a product can exceed 2³¹)

Hints

Hint 1

Checking every pair is n × m = 10¹⁰ multiplications. What would make one spell's count quick?

Hint 2

If potions are sorted, the potions that work with a given spell form a suffix: once one is strong enough, every larger one is too.

Hint 3

For each spell, find the first potion p with s × p ≥ success by binary search; the count is m minus that index.

Where people lose marks

Multiplying in 32 bits: 10⁵ × 10⁵ overflows and turns a success into a negative number.
Sorting the spells as well, which scrambles the order of the answer.
Dividing instead of multiplying with integer division: the smallest p is ⌈success / s⌉, not success / s.

Dry run on `[5,1,3],[4,1,5,2,3],7`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 11

Step 1 / 11

success7
Sort the potions once: [1, 2, 3, 4, 5]. For any spell, the potions that succeed form a suffix of this list.
Step 2 / 11

spell5lo0mid2hi5
Spell 5: 5 × 3 = 15 ≥ 7, a success: hi = 2.
Step 3 / 11

spell5lo0mid1hi2
Spell 5: 5 × 2 = 10 ≥ 7, a success: hi = 1.
Step 4 / 11

spell5lo0mid0hi1
Spell 5: 5 × 1 = 5 < 7, too weak: lo = 1.
Step 5 / 11

spell5count4
Spell 5: the first success is at index 1, so 5 − 1 = 4 potions work.
Step 6 / 11

spell1lo0mid2hi5
Spell 1: 1 × 3 = 3 < 7, too weak: lo = 3.
Step 7 / 11

spell1lo3mid4hi5
Spell 1: 1 × 5 = 5 < 7, too weak: lo = 5.
Step 8 / 11

spell1count0
Spell 1: the first success is at index 5, so 5 − 5 = 0 potions work.
Step 9 / 11

spell3lo0mid2hi5
Spell 3: 3 × 3 = 9 ≥ 7, a success: hi = 2.
Step 10 / 11

spell3lo0mid1hi2
Spell 3: 3 × 2 = 6 < 7, too weak: lo = 2.
Step 11 / 11

spell3count3
Spell 3: the first success is at index 2, so 5 − 2 = 3 potions work. The answer, in the original order of the spells, is [4, 0, 3].

How to think about it

For a fixed spell s, the test s × p ≥ success is monotone in p: a stronger potion never turns a success into a failure. So after sorting potions, the successful potions are exactly a suffix, and its length is m minus the index of the first success.

That index is a lower bound, found by binary search with the test s × potions[mid] ≥ success. Sorting costs O(m log m) once, and each spell costs O(log m), for O((n + m) log m) in total instead of O(n × m).

The general move: when many queries ask "how many items pass a threshold", sort the items once and answer each query with a boundary search. The same structure counts pairs with sum at most k, offers below a budget, or candidates within a distance.

Two details matter. The product of two values up to 10⁵ reaches 10¹⁰, beyond a 32-bit integer, so multiply in 64 bits. And the result must be in the original order of spells, so sort only the potions.

Complexity. Time O((n + m) log m) · Space O(m) for the sorted copy

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

from bisect import bisect_left

def successful_pairs(spells, potions, success):
    potions = sorted(potions)
    m = len(potions)
    out = []
    for s in spells:
        need = (success + s - 1) // s          # the weakest potion that works: ceil(success / s)
        out.append(m - bisect_left(potions, need))
    return out

#include <vector>
#include <algorithm>

std::vector<int> solve(const std::vector<int>& spells, std::vector<int> potions, long long success) {
    std::sort(potions.begin(), potions.end());
    const int m = (int)potions.size();
    std::vector<int> out;
    for (long long s : spells) {
        int lo = 0, hi = m;                       // first index with s * p[i] >= success
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (s * potions[mid] >= success) hi = mid;   // 64-bit product
            else lo = mid + 1;
        }
        out.push_back(m - lo);
    }
    return out;
}

import java.util.Arrays;

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int[] p = potions.clone();
        Arrays.sort(p);
        int m = p.length;
        int[] out = new int[spells.length];
        for (int i = 0; i < spells.length; i++) {
            long s = spells[i];
            int lo = 0, hi = m;                   // first index with s * p[j] >= success
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (s * p[mid] >= success) hi = mid;     // long product
                else lo = mid + 1;
            }
            out[i] = m - lo;
        }
        return out;
    }
}

function successfulPairs(spells, potions, success) {
  const p = potions.slice().sort((a, b) => a - b);
  const m = p.length;
  return spells.map(s => {
    let lo = 0, hi = m;                    // first index with s * p[i] >= success
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (s * p[mid] >= success) hi = mid; else lo = mid + 1;   // exact below 2^53
    }
    return m - lo;
  });
}

fn solve(spells: &[i64], potions: &[i64], success: i64) -> Vec<i64> {
    let mut p = potions.to_vec();
    p.sort();
    spells
        .iter()
        .map(|&s| (p.len() - p.partition_point(|&x| s * x < success)) as i64)
        .collect()
}

import Data.Array
import Data.List (sort)

solve :: [Int] -> [Int] -> Int -> [Int]
solve spells potions success = map count spells
  where
    m = length potions
    p = listArray (0, m - 1) (sort potions)
    -- first index with s * p[i] >= success (Int is 64-bit)
    count s = m - go 0 m
      where
        go lo hi
          | lo >= hi                 = lo
          | s * p ! mid >= success   = go lo mid
          | otherwise                = go (mid + 1) hi
          where mid = lo + (hi - lo) `div` 2

Variants to try

Sort the spells too and sweep with two pointers: O(n log n + m log m) and no searches, at the cost of remembering original positions.
Return, for each spell, the weakest successful potion instead of the count.
Count all successful pairs in total: sum the answers, or use two pointers on both sorted lists.

Next problems

Easy10 min

Count the partners that clear a threshold

Examples

Constraints

Hints

Where people lose marks

Dry run on `[5,1,3],[4,1,5,2,3],7`

How to think about it

The solution, in six languages

Variants to try

Next problems

Where a value belongs in a sorted array

First and last position of a value

Research impact from sorted citation counts

Keep going

Where a value belongs in a sorted array

First and last position of a value

Research impact from sorted citation counts

The pattern behind it

Count the partners that clear a threshold

Examples

Constraints

Hints

Where people lose marks

Dry run on [5,1,3],[4,1,5,2,3],7

How to think about it

The solution, in six languages

Variants to try

Next problems

Where a value belongs in a sorted array

First and last position of a value

Research impact from sorted citation counts

Keep going

Where a value belongs in a sorted array

First and last position of a value

Research impact from sorted citation counts

The pattern behind it

Dry run on `[5,1,3],[4,1,5,2,3],7`