Successful Pairs of Spells and Potions - Practice Coding Problems

Successful Pairs of Spells and Potions - Problem

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the i^th spell and potions[j] represents the strength of the j^th 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 i^th spell.

Input & Output

Example 1 — Basic Case

$ Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7

› Output: [4,0,3]

💡 Note: Spell 5: 5×1=5, 5×2=10≥7, 5×3=15≥7, 5×4=20≥7, 5×5=25≥7 → 4 pairs. Spell 1: all products < 7 → 0 pairs. Spell 3: 3×3=9≥7, 3×4=12≥7, 3×5=15≥7 → 3 pairs.

Example 2 — Higher Success Threshold

$ Input: spells = [3,1,2], potions = [8,5,8], success = 16

› Output: [2,0,2]

💡 Note: Spell 3: 3×8=24≥16 (appears twice) → 2 pairs. Spell 1: all products < 16 → 0 pairs. Spell 2: 2×8=16≥16 (appears twice) → 2 pairs.

Example 3 — Edge Case Small Arrays

$ Input: spells = [1], potions = [1], success = 1

› Output: [1]

💡 Note: Single spell 1 and single potion 1: 1×1=1≥1, so 1 successful pair.

Constraints

1 ≤ spells.length, potions.length ≤ 10⁵
1 ≤ spells[i], potions[i] ≤ 10⁵
1 ≤ success ≤ 10¹⁰

Visualization

Tap to expand

Understanding the Visualization

Input

Spells [5,1,3], potions [1,2,3,4,5], success = 7

Process

For each spell, count potions where spell × potion ≥ success

Output

Array of counts: [4,0,3]

Key Takeaway

🎯 Key Insight: Sort potions once, then use binary search to find the cutoff point for each spell instead of checking every pair

Asked in

M Meta 25 A Amazon 20 G Google 15

The key insight is that after sorting potions, we can use binary search to efficiently find the cutoff point for each spell. The optimal approach sorts potions once in O(m log m) time, then performs binary search for each spell in O(log m) time. Best approach is Binary Search: Time O(m log m + n log m), Space O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n×m)	O(1)	Check every spell against every potion
Binary Search (Optimal)	O(m log m + n log m)	O(1)	Sort potions once, then binary search for each spell

Brute Force — Algorithm Steps

For each spell in the array
Check it against every potion
Count successful pairs where product >= success

Visualization

Tap to expand

Step-by-Step Walkthrough

For Each Spell

Take one spell and check against all potions

Count Matches

Count how many potions make product >= success

Result

Store count for this spell and move to next

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void solution(int* spells, int spellsSize, int* potions, int potionsSize, long long success, int* result) {
    for (int i = 0; i < spellsSize; i++) {
        int count = 0;
        for (int j = 0; j < potionsSize; j++) {
            if ((long long)spells[i] * potions[j] >= success) {
                count++;
            }
        }
        result[i] = count;
    }
}

int main() {
    char line[10000];
    int spells[1000], potions[1000];
    int spellsSize = 0, potionsSize = 0;
    
    // Parse spells array
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        spells[spellsSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    // Parse potions array
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]");
    while (token != NULL) {
        potions[potionsSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    // Parse success
    fgets(line, sizeof(line), stdin);
    long long success = atoll(line);
    
    int result[1000];
    solution(spells, spellsSize, potions, potionsSize, success, result);
    
    printf("[");
    for (int i = 0; i < spellsSize; i++) {
        printf("%d", result[i]);
        if (i < spellsSize - 1) printf(",");
    }
    printf("]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

Nested loops: n spells × m potions = n×m operations

✓ Linear Growth

Space Complexity

O(1)

Only using variables for counting, no extra data structures

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler