2300. Successful Pairs of Spells and Potions - Explanation

Description

A spell and a potion form a successful pair when the product of their strengths is at least success. For each value in spells, count how many entries of potions form a successful pair with it. Return those counts in the same order as spells. Repeated potion strengths count separately, and the same potion can be counted for multiple spells.

Example 1:

Input: spells = [2,5,1]
potions = [2,3,6]
success = 10

Output: [1,3,0]

Explanation: The spell of strength 2 succeeds only with potion 6. The spell of strength 5 succeeds with all three potions, while the spell of strength 1 succeeds with none. Return [1,3,0].

Example 2:

Input: spells = [4,2]
potions = [3,3,5]
success = 12

Output: [3,0]

Explanation: For strength 4, both potions of strength 3 and the potion of strength 5 succeed. Neither strength-3 potion nor strength-5 potion succeeds with the spell of strength 2, so return [3,0].

Example 3:

Input: spells = [1,100000]
potions = [1,100000]
success = 10000000000

Output: [0,1]

Explanation: A spell of strength 1 cannot reach the threshold. The strength-100000 spell succeeds only with the strength-100000 potion, whose product is exactly 10000000000. Return [0,1].

Constraints:

1 <= spells.length, potions.length <= 100000
1 <= spells[i], potions[i] <= 100000
1 <= success <= 10000000000

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sorting - Required to arrange potions in order so that successful pairs form a contiguous range
Binary Search - Used to efficiently find the threshold index where potions become successful
Two Pointers - Alternative approach processes sorted spells and potions simultaneously

1. Brute Force

Intuition

For each spell, we need to count how many potions form a successful pair. A pair is successful when spell * potion >= success. The simplest approach is to check every spell against every potion and count the valid combinations.

Algorithm

Create a result array res to store the count for each spell.
For each spell s in spells:
- Initialize a counter cnt = 0.
- For each potion p in potions:
  - If s * p >= success, increment cnt.
- Append cnt to res.
Return res.

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        res = []

        for s in spells:
            cnt = 0
            for p in potions:
                if s * p >= success:
                    cnt += 1
            res.append(cnt)

        return res

public class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int[] res = new int[spells.length];

        for (int i = 0; i < spells.length; i++) {
            int cnt = 0;
            for (int p : potions) {
                if ((long) spells[i] * p >= success) {
                    cnt++;
                }
            }
            res[i] = cnt;
        }

        return res;
    }
}

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        vector<int> res(spells.size());

        for (int i = 0; i < spells.size(); i++) {
            int cnt = 0;
            for (int p : potions) {
                if ((long long) spells[i] * p >= success) {
                    cnt++;
                }
            }
            res[i] = cnt;
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} spells
     * @param {number[]} potions
     * @param {number} success
     * @return {number[]}
     */
    successfulPairs(spells, potions, success) {
        let res = [];

        for (let s of spells) {
            let cnt = 0;
            for (let p of potions) {
                if (s * p >= success) {
                    cnt++;
                }
            }
            res.push(cnt);
        }

        return res;
    }
}

public class Solution {
    public int[] SuccessfulPairs(int[] spells, int[] potions, long success) {
        int[] res = new int[spells.Length];

        for (int i = 0; i < spells.Length; i++) {
            int cnt = 0;
            foreach (int p in potions) {
                if ((long)spells[i] * p >= success) {
                    cnt++;
                }
            }
            res[i] = cnt;
        }

        return res;
    }
}

func successfulPairs(spells []int, potions []int, success int64) []int {
    res := make([]int, len(spells))

    for i, s := range spells {
        cnt := 0
        for _, p := range potions {
            if int64(s)*int64(p) >= success {
                cnt++
            }
        }
        res[i] = cnt
    }

    return res
}

class Solution {
    fun successfulPairs(spells: IntArray, potions: IntArray, success: Long): IntArray {
        val res = IntArray(spells.size)

        for (i in spells.indices) {
            var cnt = 0
            for (p in potions) {
                if (spells[i].toLong() * p >= success) {
                    cnt++
                }
            }
            res[i] = cnt
        }

        return res
    }
}

class Solution {
    func successfulPairs(_ spells: [Int], _ potions: [Int], _ success: Int) -> [Int] {
        var res = [Int]()

        for s in spells {
            var cnt = 0
            for p in potions {
                if s * p >= success {
                    cnt += 1
                }
            }
            res.append(cnt)
        }

        return res
    }
}

impl Solution {
    pub fn successful_pairs(spells: Vec<i32>, potions: Vec<i32>, success: i64) -> Vec<i32> {
        let mut res = Vec::with_capacity(spells.len());

        for &s in &spells {
            let mut cnt = 0;
            for &p in &potions {
                if s as i64 * p as i64 >= success {
                    cnt += 1;
                }
            }
            res.push(cnt);
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(1)$

The output array is not counted towards space complexity, as the standard convention measures only auxiliary working space.

Where $n$ and $m$ are the sizes of the arrays $spells$ and $potions$ respectively.

2. Sorting + Binary Search

Intuition

If we sort the potions array, all successful potions for a given spell will be contiguous at the end. For a spell s, we need the minimum potion strength p such that s * p >= success, which means p >= success / s. Binary search can efficiently find this threshold index, and all potions from that index onward form successful pairs.

Algorithm

Sort the potions array in ascending order.
For each spell s in spells:
- Use binary search to find the smallest index idx where s * potions[idx] >= success.
- The count of successful pairs is len(potions) - idx.
- Store this count in the result.
Return the result array.

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()
        res = []

        for s in spells:
            l, r = 0, len(potions) - 1
            idx = len(potions)

            while l <= r:
                m = (l + r) // 2
                if s * potions[m] >= success:
                    r = m - 1
                    idx = m
                else:
                    l = m + 1

            res.append(len(potions) - idx)

        return res

public class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int[] res = new int[spells.length];

        for (int i = 0; i < spells.length; i++) {
            int l = 0, r = potions.length - 1, idx = potions.length;

            while (l <= r) {
                int m = (l + r) / 2;
                if ((long) spells[i] * potions[m] >= success) {
                    r = m - 1;
                    idx = m;
                } else {
                    l = m + 1;
                }
            }

            res[i] = potions.length - idx;
        }

        return res;
    }
}

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        sort(potions.begin(), potions.end());
        vector<int> res(spells.size());

        for (int i = 0; i < spells.size(); i++) {
            int l = 0, r = potions.size() - 1, idx = potions.size();

            while (l <= r) {
                int m = (l + r) / 2;
                if ((long long) spells[i] * potions[m] >= success) {
                    r = m - 1;
                    idx = m;
                } else {
                    l = m + 1;
                }
            }

            res[i] = potions.size() - idx;
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} spells
     * @param {number[]} potions
     * @param {number} success
     * @return {number[]}
     */
    successfulPairs(spells, potions, success) {
        potions.sort((a, b) => a - b);
        let res = [];

        for (let s of spells) {
            let l = 0,
                r = potions.length - 1,
                idx = potions.length;

            while (l <= r) {
                let m = Math.floor((l + r) / 2);
                if (s * potions[m] >= success) {
                    r = m - 1;
                    idx = m;
                } else {
                    l = m + 1;
                }
            }

            res.push(potions.length - idx);
        }

        return res;
    }
}

public class Solution {
    public int[] SuccessfulPairs(int[] spells, int[] potions, long success) {
        Array.Sort(potions);
        int[] res = new int[spells.Length];

        for (int i = 0; i < spells.Length; i++) {
            int l = 0, r = potions.Length - 1, idx = potions.Length;

            while (l <= r) {
                int m = (l + r) / 2;
                if ((long)spells[i] * potions[m] >= success) {
                    r = m - 1;
                    idx = m;
                } else {
                    l = m + 1;
                }
            }

            res[i] = potions.Length - idx;
        }

        return res;
    }
}

func successfulPairs(spells []int, potions []int, success int64) []int {
    sort.Ints(potions)
    res := make([]int, len(spells))

    for i, s := range spells {
        l, r, idx := 0, len(potions)-1, len(potions)

        for l <= r {
            m := (l + r) / 2
            if int64(s)*int64(potions[m]) >= success {
                r = m - 1
                idx = m
            } else {
                l = m + 1
            }
        }

        res[i] = len(potions) - idx
    }

    return res
}

class Solution {
    fun successfulPairs(spells: IntArray, potions: IntArray, success: Long): IntArray {
        potions.sort()
        val res = IntArray(spells.size)

        for (i in spells.indices) {
            var l = 0
            var r = potions.size - 1
            var idx = potions.size

            while (l <= r) {
                val m = (l + r) / 2
                if (spells[i].toLong() * potions[m] >= success) {
                    r = m - 1
                    idx = m
                } else {
                    l = m + 1
                }
            }

            res[i] = potions.size - idx
        }

        return res
    }
}

class Solution {
    func successfulPairs(_ spells: [Int], _ potions: [Int], _ success: Int) -> [Int] {
        let sortedPotions = potions.sorted()
        var res = [Int]()

        for s in spells {
            var l = 0
            var r = sortedPotions.count - 1
            var idx = sortedPotions.count

            while l <= r {
                let m = (l + r) / 2
                if s * sortedPotions[m] >= success {
                    r = m - 1
                    idx = m
                } else {
                    l = m + 1
                }
            }

            res.append(sortedPotions.count - idx)
        }

        return res
    }
}

impl Solution {
    pub fn successful_pairs(spells: Vec<i32>, mut potions: Vec<i32>, success: i64) -> Vec<i32> {
        potions.sort();
        let m = potions.len();
        let mut res = Vec::with_capacity(spells.len());

        for &s in &spells {
            let mut l = 0i32;
            let mut r = m as i32 - 1;
            let mut idx = m;

            while l <= r {
                let mid = ((l + r) / 2) as usize;
                if s as i64 * potions[mid] as i64 >= success {
                    r = mid as i32 - 1;
                    idx = mid;
                } else {
                    l = mid as i32 + 1;
                }
            }

            res.push((m - idx) as i32);
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O((m + n) * \log m)$
Space complexity:
- $O(1)$ or $O(m)$ extra space depending on the sorting algorithm.
- $O(n)$ space for the output array.

Where $n$ and $m$ are the sizes of the arrays $spells$ and $potions$ respectively.

3. Sorting + Two Pointers

Intuition

If we sort both arrays, we can use the two pointer technique. A weaker spell needs a stronger potion to succeed, and a stronger spell needs at least as weak a potion. By processing spells in ascending order and potions in descending order, we can reuse the potion pointer position. Once a potion works for a spell, it works for all stronger spells too.

Algorithm

Save the original spells array and sort both spells and potions.
Use a pointer j starting at the end of sorted potions.
For each spell in sorted order:
- Move j left while spell * potions[j] >= success.
- Store the count m - j - 1 in a map keyed by spell strength.
Build the result by looking up each original spell's count in the map.
Return the result.

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        n, m = len(spells), len(potions)
        S = spells[:]
        count = defaultdict(int)
        spells.sort()
        potions.sort()

        j = m - 1
        for i in range(n):
            while j >= 0 and spells[i] * potions[j] >= success:
                j -= 1
            count[spells[i]] = m - j - 1

        res = [0] * n
        for i in range(n):
            res[i] = count[S[i]]

        return res

public class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length, m = potions.length;
        int[] S = Arrays.copyOf(spells, n);
        Map<Integer, Integer> count = new HashMap<>();
        Arrays.sort(spells);
        Arrays.sort(potions);

        int j = m - 1;
        for (int i = 0; i < n; i++) {
            while (j >= 0 && (long) spells[i] * potions[j] >= success) {
                j--;
            }
            count.put(spells[i], m - j - 1);
        }

        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = count.get(S[i]);
        }

        return res;
    }
}

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        int n = spells.size(), m = potions.size();
        vector<int> S = spells;
        unordered_map<int, int> count;
        sort(spells.begin(), spells.end());
        sort(potions.begin(), potions.end());

        int j = m - 1;
        for (int i = 0; i < n; i++) {
            while (j >= 0 && (long long) spells[i] * potions[j] >= success) {
                j--;
            }
            count[spells[i]] = m - j - 1;
        }

        vector<int> res(n);
        for (int i = 0; i < n; i++) {
            res[i] = count[S[i]];
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} spells
     * @param {number[]} potions
     * @param {number} success
     * @return {number[]}
     */
    successfulPairs(spells, potions, success) {
        const n = spells.length,
            m = potions.length;
        const S = [...spells];
        const count = new Map();
        spells.sort((a, b) => a - b);
        potions.sort((a, b) => a - b);

        let j = m - 1;
        for (let i = 0; i < n; i++) {
            while (j >= 0 && spells[i] * potions[j] >= success) {
                j--;
            }
            count.set(spells[i], m - j - 1);
        }

        return S.map((s) => count.get(s));
    }
}

public class Solution {
    public int[] SuccessfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.Length, m = potions.Length;
        int[] S = (int[])spells.Clone();
        Dictionary<int, int> count = new Dictionary<int, int>();
        Array.Sort(spells);
        Array.Sort(potions);

        int j = m - 1;
        for (int i = 0; i < n; i++) {
            while (j >= 0 && (long)spells[i] * potions[j] >= success) {
                j--;
            }
            count[spells[i]] = m - j - 1;
        }

        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = count[S[i]];
        }

        return res;
    }
}

func successfulPairs(spells []int, potions []int, success int64) []int {
    n, m := len(spells), len(potions)
    S := make([]int, n)
    copy(S, spells)
    count := make(map[int]int)
    sort.Ints(spells)
    sort.Ints(potions)

    j := m - 1
    for i := 0; i < n; i++ {
        for j >= 0 && int64(spells[i])*int64(potions[j]) >= success {
            j--
        }
        count[spells[i]] = m - j - 1
    }

    res := make([]int, n)
    for i := 0; i < n; i++ {
        res[i] = count[S[i]]
    }

    return res
}

class Solution {
    fun successfulPairs(spells: IntArray, potions: IntArray, success: Long): IntArray {
        val n = spells.size
        val m = potions.size
        val S = spells.copyOf()
        val count = HashMap<Int, Int>()
        spells.sort()
        potions.sort()

        var j = m - 1
        for (i in 0 until n) {
            while (j >= 0 && spells[i].toLong() * potions[j] >= success) {
                j--
            }
            count[spells[i]] = m - j - 1
        }

        return IntArray(n) { count[S[it]]!! }
    }
}

class Solution {
    func successfulPairs(_ spells: [Int], _ potions: [Int], _ success: Int) -> [Int] {
        let n = spells.count, m = potions.count
        let S = spells
        var count = [Int: Int]()
        let sortedSpells = spells.sorted()
        let sortedPotions = potions.sorted()

        var j = m - 1
        for i in 0..<n {
            while j >= 0 && sortedSpells[i] * sortedPotions[j] >= success {
                j -= 1
            }
            count[sortedSpells[i]] = m - j - 1
        }

        return S.map { count[$0]! }
    }
}

impl Solution {
    pub fn successful_pairs(spells: Vec<i32>, potions: Vec<i32>, success: i64) -> Vec<i32> {
        let n = spells.len();
        let m = potions.len();
        let original = spells.clone();
        let mut sorted_spells = spells;
        let mut sorted_potions = potions;
        sorted_spells.sort();
        sorted_potions.sort();

        let mut count = HashMap::new();
        let mut j = m as i32 - 1;

        for i in 0..n {
            while j >= 0
                && sorted_spells[i] as i64 * sorted_potions[j as usize] as i64 >= success
            {
                j -= 1;
            }
            count.insert(sorted_spells[i], (m as i32 - j - 1));
        }

        original.iter().map(|s| *count.get(s).unwrap()).collect()
    }
}

Time & Space Complexity

Time complexity: $O(n \log n + m\log m)$
Space complexity:
- $O(1)$ or $O(m + n)$ extra space depending on the sorting algorithm.
- $O(n)$ space for the output array.

Where $n$ and $m$ are the sizes of the arrays $spells$ and $potions$ respectively.

4. Sorting + Two Pointers (Optimal)

Intuition

The previous approach uses extra space to map spell values to their counts. We can avoid this by sorting indices of spells rather than the spells themselves. This way, we can directly write results to the correct positions in the output array without needing a lookup map.

Algorithm

Create an array of indices sIdx and sort it by corresponding spell strength.
Sort the potions array.
Initialize pointer j at the end of potions and result array res.
For each index i in sorted order:
- Move j left while spells[sIdx[i]] * potions[j] >= success.
- Set res[sIdx[i]] = m - j - 1.
Return res.

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        n, m = len(spells), len(potions)
        sIdx = list(range(n))
        sIdx.sort(key=lambda x: spells[x])
        potions.sort()

        j = m - 1
        res = [0] * n
        for i in range(n):
            while j >= 0 and spells[sIdx[i]] * potions[j] >= success:
                j -= 1
            res[sIdx[i]] = m - j - 1

        return res

public class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length, m = potions.length;
        Integer[] sIdx = new Integer[n];
        for (int i = 0; i < n; i++) sIdx[i] = i;

        Arrays.sort(sIdx, Comparator.comparingInt(i -> spells[i]));
        Arrays.sort(potions);

        int j = m - 1;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            while (j >= 0 && (long) spells[sIdx[i]] * potions[j] >= success) {
                j--;
            }
            res[sIdx[i]] = m - j - 1;
        }

        return res;
    }
}

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        int n = spells.size(), m = potions.size();
        vector<int> sIdx(n);
        for (int i = 0; i < n; i++) sIdx[i] = i;

        sort(sIdx.begin(), sIdx.end(), [&](int a, int b) {
            return spells[a] < spells[b];
        });

        sort(potions.begin(), potions.end());

        int j = m - 1;
        vector<int> res(n);
        for (int i = 0; i < n; i++) {
            while (j >= 0 && (long long) spells[sIdx[i]] * potions[j] >= success) {
                j--;
            }
            res[sIdx[i]] = m - j - 1;
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} spells
     * @param {number[]} potions
     * @param {number} success
     * @return {number[]}
     */
    successfulPairs(spells, potions, success) {
        const n = spells.length,
            m = potions.length;
        const sIdx = Array.from({ length: n }, (_, i) => i);

        sIdx.sort((a, b) => spells[a] - spells[b]);
        potions.sort((a, b) => a - b);

        let j = m - 1;
        const res = new Array(n).fill(0);

        for (let i = 0; i < n; i++) {
            while (j >= 0 && spells[sIdx[i]] * potions[j] >= success) {
                j--;
            }
            res[sIdx[i]] = m - j - 1;
        }

        return res;
    }
}

public class Solution {
    public int[] SuccessfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.Length, m = potions.Length;
        int[] sIdx = new int[n];
        for (int i = 0; i < n; i++) sIdx[i] = i;

        Array.Sort(sIdx, (a, b) => spells[a].CompareTo(spells[b]));
        Array.Sort(potions);

        int j = m - 1;
        int[] res = new int[n];

        for (int i = 0; i < n; i++) {
            while (j >= 0 && (long)spells[sIdx[i]] * potions[j] >= success) {
                j--;
            }
            res[sIdx[i]] = m - j - 1;
        }

        return res;
    }
}

func successfulPairs(spells []int, potions []int, success int64) []int {
    n, m := len(spells), len(potions)
    sIdx := make([]int, n)
    for i := range sIdx {
        sIdx[i] = i
    }

    sort.Slice(sIdx, func(i, j int) bool {
        return spells[sIdx[i]] < spells[sIdx[j]]
    })
    sort.Ints(potions)

    j := m - 1
    res := make([]int, n)

    for i := 0; i < n; i++ {
        for j >= 0 && int64(spells[sIdx[i]])*int64(potions[j]) >= success {
            j--
        }
        res[sIdx[i]] = m - j - 1
    }

    return res
}

class Solution {
    fun successfulPairs(spells: IntArray, potions: IntArray, success: Long): IntArray {
        val n = spells.size
        val m = potions.size
        val sIdx = (0 until n).sortedBy { spells[it] }
        potions.sort()

        var j = m - 1
        val res = IntArray(n)

        for (i in 0 until n) {
            while (j >= 0 && spells[sIdx[i]].toLong() * potions[j] >= success) {
                j--
            }
            res[sIdx[i]] = m - j - 1
        }

        return res
    }
}

class Solution {
    func successfulPairs(_ spells: [Int], _ potions: [Int], _ success: Int) -> [Int] {
        let n = spells.count, m = potions.count
        let sIdx = (0..<n).sorted { spells[$0] < spells[$1] }
        let sortedPotions = potions.sorted()

        var j = m - 1
        var res = [Int](repeating: 0, count: n)

        for i in 0..<n {
            while j >= 0 && spells[sIdx[i]] * sortedPotions[j] >= success {
                j -= 1
            }
            res[sIdx[i]] = m - j - 1
        }

        return res
    }
}

impl Solution {
    pub fn successful_pairs(spells: Vec<i32>, mut potions: Vec<i32>, success: i64) -> Vec<i32> {
        let n = spells.len();
        let m = potions.len();
        let mut s_idx: Vec<usize> = (0..n).collect();
        s_idx.sort_by_key(|&i| spells[i]);
        potions.sort();

        let mut j = m as i32 - 1;
        let mut res = vec![0i32; n];

        for i in 0..n {
            while j >= 0
                && spells[s_idx[i]] as i64 * potions[j as usize] as i64 >= success
            {
                j -= 1;
            }
            res[s_idx[i]] = m as i32 - j - 1;
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n \log n + m\log m)$
Space complexity:
- $O(1)$ or $O(m + n)$ extra space depending on the sorting algorithm.
- $O(n)$ space for the output array.

Where $n$ and $m$ are the sizes of the arrays $spells$ and $potions$ respectively.

Common Pitfalls

Integer Overflow in Multiplication

When multiplying spell * potion, the result can exceed the range of a 32-bit integer since both values can be up to 10^5, making the product up to 10^10. Always cast to long before multiplication or use a 64-bit integer type to avoid overflow and incorrect comparisons.

Off-by-One Errors in Binary Search

A common mistake is incorrectly calculating the count of successful pairs after binary search. The binary search finds the first index where the condition is satisfied, and the count should be len(potions) - idx. Errors occur when using <= vs < in the binary search condition or when the index represents the wrong boundary.

Forgetting to Sort the Potions Array

Binary search only works on sorted arrays. A frequent oversight is attempting to use binary search on the original unsorted potions array, which leads to incorrect results. The potions array must be sorted first, and for the two-pointer approach, both arrays need to be sorted while preserving the original spell order for the output.