Successful Pairs of Spells and Potions

MediumBinary Searchbinary search

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You have two positive integer arrays: spells of length n, where spells[i] is the strength of spell i, and potions of length m, where potions[j] is the strength of potion j. A spell and a potion form a **successful** pair when the product of their strengths is at least success. Return an array pairs of length n where pairs[i] is the number of potions that form a successful pair with spell i. The output stays in the same order as spells. Products can exceed the 32-bit range, and success itself may be up to 10^10. Aim for O((n + m) log m) time.

Examples

Input: spells = [4,1,3], potions = [1,2,3,4,5], success = 8
Output: [4,0,3]
Spell `4` gives products `4,8,12,16,20` (4 reach 8). Spell `1` never reaches 8. Spell `3` gives `3,6,9,12,15` (3 reach 8).
Input: spells = [2,6], potions = [7,1,3], success = 12
Output: [1,2]
Spell `2` succeeds only with potion `7` (14). Spell `6` succeeds with `7` (42) and `3` (18).

Constraints

  • 1 <= spells.length, potions.length <= 10^5
  • 1 <= spells[i], potions[j] <= 10^5
  • 1 <= success <= 10^10

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More binary search problems