Skip to main content

22. Successful Pairs of Spells and Potions

mediumAsked at Flipkart

For each spell strength, count potions whose product meets a success threshold — Flipkart uses this binary-search-on-sorted-array pattern for offer-eligibility checks during sale events.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given arrays spells and potions of positive integers and a long success threshold, return an array pairs where pairs[i] is the number of potions that form a successful pair with spells[i] (spells[i] * potions[j] >= success).

Constraints

  • 1 <= n, m <= 10^5
  • 1 <= spells[i], potions[j] <= 10^5
  • 1 <= success <= 10^10

Examples

Example 1

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

Example 2

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

Approaches

1. Brute force

For each spell, scan every potion.

Time
O(n*m)
Space
O(1)
// nested loop; times out at the upper bound

Tradeoff:

2. Sort + binary search

Sort potions. For each spell, compute the threshold (ceil(success / spell)) and binary-search the lower bound; everything from that index forward succeeds.

Time
O((n+m) log m)
Space
O(1)
function successfulPairs(spells, potions, success) {
  potions.sort((a, b) => a - b);
  const m = potions.length;
  return spells.map(s => {
    let lo = 0, hi = m;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (BigInt(potions[mid]) * BigInt(s) >= BigInt(success)) hi = mid;
      else lo = mid + 1;
    }
    return m - lo;
  });
}

Tradeoff:

Flipkart-specific tips

Flipkart panels reward the BigInt callout — multiplying spells * potions easily overflows 2^53 and they have hit that boundary in offer-eligibility checks.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Successful Pairs of Spells and Potions and other Flipkart interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →