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

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

✓ Binary Search (Optimal)

⏱️ Time: O(m log m + n log m) Space: O(1)

Sort the potions array first. For each spell, use binary search to find the smallest potion where spell * potion >= success. All potions from that position onwards will form successful pairs.

Brute Force

⏱️ Time: O(n×m) Space: O(1)

For each spell, iterate through all potions and count how many form successful pairs. This means checking if spell[i] * potion[j] >= success for every combination.

Binary Search (Optimal) — Algorithm Steps

Sort the potions array in ascending order
For each spell, calculate minimum potion needed: ceil(success/spell)
Use binary search to find first potion >= minimum
Count = total potions - found index

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Potions

Sort potions in ascending order

Binary Search

For each spell, find first valid potion

Count

All potions from that point onwards are valid

Code -

solution.c — C

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

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int binarySearch(int* arr, int size, long long target) {
    int left = 0, right = size;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

void solution(int* spells, int spellsSize, int* potions, int potionsSize, long long success, int* result) {
    qsort(potions, potionsSize, sizeof(int), compare);
    
    for (int i = 0; i < spellsSize; i++) {
        long long minPotion = (success + spells[i] - 1) / spells[i];
        int idx = binarySearch(potions, potionsSize, minPotion);
        result[i] = potionsSize - idx;
    }
}

void parseArray(const char* str, int* arr, int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p) p++; // skip '['
    
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',' || *p == '\n') p++;
        if (*p == ']' || *p == '\0') break;
        
        char* endptr;
        long val = strtol(p, &endptr, 10);
        if (endptr != p) {
            arr[(*size)++] = (int)val;
            p = endptr;
        } else {
            p++;
        }
    }
}

int main() {
    char line[10000];
    int spells[1000], potions[1000];
    int spellsSize = 0, potionsSize = 0;
    
    // Read spells array
    fgets(line, sizeof(line), stdin);
    parseArray(line, spells, &spellsSize);
    
    // Read potions array
    fgets(line, sizeof(line), stdin);
    parseArray(line, potions, &potionsSize);
    
    // Read success value
    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(m log m + n log m)

Sorting potions takes O(m log m), then n binary searches each taking O(log m)

✓ Linear Growth

Space Complexity

O(1)

Only using variables for binary search, sorting is in-place

✓ 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

Successful Pairs of Spells and Potions - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler