Leetcode - 2300. Successful Pairs of Spells and Potions - JavaScript

maksimdygai — Mon, 03 Apr 2023 11:32:17 +0000

The 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 1

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.

Example 2

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.

Idea

We need to check how every spell works with potions. But for the latter, we don't need to check every one. Instead, we can sort the array and stop checking at the element which gives us the result greater than success. Traversing the sorted array based on binary search will give the best possible time complexity.

Implementation

var successfulPairs = function(spells, potions, success) {
    let result = [];

    potions.sort((a, b) => a - b);

    for(const spell of spells) {
        let l = 0;
        let r = potions.length - 1;
        let count = potions.length;

        while(l <= r) {
            let m = Math.floor((l + r) / 2);

            if(spell * potions[m] >= success) {
                r = m - 1;
                count = m;
            } else {
                l = m + 1;
            }
        }

        result.push(potions.length - count);
    }

    return result;
};

The solution works in O(nlogm + mlogm) time complexity and explained in this video (Python version) by NeetCodeIO

DEV Community: maksimdygai

Leetcode - 2300. Successful Pairs of Spells and Potions - JavaScript