DDSA Solutions

2300. Successful Pairs of Spells and Potions

MediumView on LeetCode
ArrayTwo PointersBinary SearchSorting

Problem Overview

For each spell (power), count potions that form successful pair: spell * potion >= success.

Intuition

For each spell (power), count potions that form successful pair: spell * potion >= success. Binary search on sorted potions.

Algorithm

  1. 1Sort potions. For each spell s: find first potion p where s * p >= success using binary search. Count = potions.length - idx.

Common Pitfalls

  • •Binary search for ceil(success / spell) in sorted potions. Handle integer overflow with long.
2300.cs
C#
// Approach: Sort potions; binary search for first potion where spell * potion >= success.
// Time: O((n + m) log m) Space: O(1)

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

        for (int i = 0; i < spells.Length; ++i)
            ans[i] = potions.Length - FirstIndexSuccess(spells[i], potions, success);

        return ans;
    }

    // Returns the first index i s.t. spell * potions[i] >= success.
    private int FirstIndexSuccess(int spell, int[] potions, long success)
    {
        int l = 0;
        int r = potions.Length;
        while (l < r)
        {
            int m = (l + r) / 2;
            if ((long)spell * potions[m] >= success)
                r = m;
            else
                l = m + 1;
        }
        return l;
    }
}
Was this solution helpful?

Related Problems