[LeetCode] 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 ith spell and potions[j] represents the strength of the jth 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 ith spell.

Example:

Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation:
- 0th spell: 5 * [1,2,3,4,5] = [5,10,15,20,25]. 4 pairs are successful.
- 1st spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
- 2nd spell: 3 * [1,2,3,4,5] = [3,6,9,12,15]. 3 pairs are successful.
Thus, [4,0,3] is returned.

Input: spells = [3,1,2], potions = [8,5,8], success = 16
Output: [2,0,2]
Explanation:
- 0th spell: 3 * [8,5,8] = [24,15,24]. 2 pairs are successful.
- 1st spell: 1 * [8,5,8] = [8,5,8]. 0 pairs are successful. 
- 2nd spell: 2 * [8,5,8] = [16,10,16]. 2 pairs are successful. 
Thus, [2,0,2] is returned.

Constraints:

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

Approach: We can use binary search here. We can simply sort the potions array and then for every spell, we try to get the first index in the potions which satisfy following condition:

spell * potions[index] >= success

Once we get this index, we can simply say that for a particular spell the number of successful pairs is m - index.

That's all!

Implementation in C#:

    public int[] SuccessfulPairs(int[] spells, int[] potions, long success)

    {

        Array.Sort(potions);

        int[] result = new int[spells.Length];

        for (int i = 0; i < spells.Length; ++i)

        {

            result[i] = this.GetNumOfPotions(spells[i], potions, success);

        }

        return result;

    }

    private int GetNumOfPotions(int spell, int[] potions, long success)

    {

        int start = 0, end = potions.Length - 1;

        while (start <= end)

        {

            int mid = start + (end - start) / 2;

            long currValue = (long)spell * potions[mid];

            if (currValue < success)

            {

                start = mid + 1;

            }

            else

            {

                end = mid - 1;

            }

        }

        return potions.Length - start;

    }

Complexity: O(mlogm + nlogm)