Successful Pairs of Spells and Potions

class Solution {
public:
    vector<int> calculatePairs(vector<int>& spells, vector<int>& potions, long long successThreshold) {
        vector<pair<int,int>> indexSpells;
        for (int i = 0; i < spells.size(); ++i) {
            indexSpells.push_back({ spells[i], i });
        }

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

        vector<int> result(spells.size());
        int n = potions.size();
        int lastPotionIndex = n - 1;
        
        for (const auto& [spell, idx] : indexSpells) {
            while (lastPotionIndex >= 0 && (long long) spell * potions[lastPotionIndex] >= successThreshold) {
                lastPotionIndex -= 1;
            }
            result[idx] = n - (lastPotionIndex + 1);
        }
        
        return result;
    }
};

The solution, implemented in C++, addresses the problem of finding successful pairs of spells and potions that meet a given success threshold. Here’s a concise breakdown of the implemented functionality:

• First, each spell and its index from the spells array are paired and stored in indexSpells.
• Both indexSpells and potions arrays are sorted. Sorting indexSpells helps in maintaining the original index of spells which is crucial for storing the result in the correct order.
• The solution utilizes a two-pointer technique after sorting, where it starts checking from the end of the sorted potions to efficiently find the count of potions that, when multiplied by the current spell, exceed the success threshold.
• For each spell in the sorted indexSpells array:
  • The inner while loop decrements the lastPotionIndex, moving backwards through potions as long as the product of the current spell and the potion at lastPotionIndex meets or exceeds the success threshold.
  • The count of valid potions for the current spell is then calculated and stored in the result array at the correct index (preserving the original order).
  • This optimization reduces the number of comparisons and leverages the benefits of sorting, resulting in significant performance improvements for large inputs.

The resulting vector<int>, result, contains the counts of successful potion pairs for each spell in their original order as input. This solution optimizes the checking process and also manages to keep track of the counts effectively for each spell.

class Solution {
    public int[] findSuccessfulPairs(int[] spells, int[] potions, long threshold) {
        int spellsCount = spells.length;
        int potionsCount = potions.length;
        
        int[][] indexedSpells = new int[spellsCount][2];
        for (int i = 0; i < spellsCount; i++) {
            indexedSpells[i][0] = spells[i];
            indexedSpells[i][1] = i;
        }
        
        Arrays.sort(indexedSpells, (a, b) -> Integer.compare(a[0], b[0]));
        Arrays.sort(potions);
        
        int[] result = new int[spellsCount];
        int eligiblePotionIndex = potionsCount - 1;

        for (int[] indexedSpell : indexedSpells) {
            int spellPower = indexedSpell[0];
            int respIndex = indexedSpell[1];

            while (eligiblePotionIndex >= 0 && (long) spellPower * potions[eligiblePotionIndex] >= threshold) {
                eligiblePotionIndex -= 1;
            }
            result[respIndex] = potionsCount - (eligiblePotionIndex + 1);
        }
        
        return result;
    }
}

To solve the problem of finding successful pairs of spells and potions, the provided Java solution follows these logical steps:

1. Initialize counts for the lengths of spells and potions arrays.
2. Create an indexed array for spells that includes both the spell's value and its original index.
3. Sort the indexed spells array based on the spell values and sort the potions array in natural order.
4. Initialize a result array to store the count of successful pairings for each spell.
5. For each spell in the sorted indexed spells array:
   • Use a while loop to check if the product of the spell's power and potions' values meets or exceeds the given threshold. Start from the end of the potions array and work backwards, validating each potion's effectiveness with the current spell.
   • Calculate the count of valid potions for the current spell by subtracting the index of the last valid potion from the total number of potions.
   • Store this count in the result array using the original index of the spell.
6. Return the result array, which now contains the number of successful pairings for each spell in the original order they appeared.

This method efficiently pairs spells with potions by sorting and then using a single traversal of the potions array, optimizing the solution by reducing unnecessary comparisons.

var findSuccessfulPairs = function(spellsList, potionList, requiredScore) {
    let indexedSpells = [];
    for (let i = 0; i < spellsList.length; i++) {
        indexedSpells.push([spellsList[i], i]);
    }

    // Sorting both the lists
    indexedSpells.sort((a, b) => a[0] - b[0]);
    potionList.sort((a, b) => a - b);

    let res = new Array(spellsList.length).fill(0);
    let totalPotions = potionList.length;
    let lastPotionIndex = totalPotions - 1;

    // Computing the number of possible pairs for each spell
    for (const [currentSpell, idx] of indexedSpells) {
        while (lastPotionIndex >= 0 && (currentSpell * potionList[lastPotionIndex]) >= requiredScore) {
            lastPotionIndex -= 1;
        }
        res[idx] = totalPotions - (lastPotionIndex + 1);
    }
    
    return res;
};

This solution outlines a JavaScript function findSuccessfulPairs designed to count the number of successful pairs of spells and potions based on a required score. Each spell from the spellsList is paired with potions from the potionList, and a pair is deemed successful if their product meets or exceeds the requiredScore.

Following is a step-by-step explanation of how the function works:

1. Initialize an empty array indexedSpells to store spells along with their initial indices.
2. Loop through each spell in the spellsList and add the spell along with its index to indexedSpells.
3. Sort indexedSpells by spells in ascending order for binary-like search efficiency.
4. Sort the potionList in ascending order to facilitate the search of valid pairs.
5. Create an array res initialized with zeros, sized to match the number of spells. This array will store the successful pairs count for each spell.
6. Define totalPotions as the length of the potionList.
7. Start from the end of the sorted potionList with lastPotionIndex.
8. Employ a reverse traverse strategy by iterating through each spell in the indexedSpells. For each spell, loop backward through the potionList starting from lastPotionIndex to find the last potion that when multiplied with the current spell surpasses the requiredScore.
9. For each spell, decrement lastPotionIndex until the product of the spell and the potion at this index is less than requiredScore.
10. The position of lastPotionIndex + 1 will give the total count of potions that can form successful pairs, which is stored in the corresponding index in res.
11. The process repeats for every spell, optimizing by not resetting lastPotionIndex but rather continuing where the last loop iteration left off.

Finally, the function returns the array res, containing the counts of successful pairs for each spell respectively.

This solution efficiently computes the desired counts with a mix of sorting, indexing, and optimized traversal, catering especially to scenarios where direct computation might be inefficient due to large input sizes.

class Solution:
    def findSuccessfulPairs(self, magic: List[int], elixirs: List[int], threshold: int) -> List[int]:
        indexedMagic = [(cast, idx) for idx, cast in enumerate(magic)]

        # Sorting spell-casts with their indices and elixirs.
        indexedMagic.sort()
        elixirs.sort()

        result = [0] * len(magic)
        totalElixirs = len(elixirs)
        lastValid = totalElixirs - 1
        
        # Checking for each spell's success with the elixirs.
        for spell, idx in indexedMagic:
            while lastValid >= 0 and (spell * elixirs[lastValid]) >= threshold:
                lastValid -= 1
            result[idx] = totalElixirs - (lastValid + 1)
        
        return result

The solution implements a function findSuccessfulPairs in Python to determine the number of successful pairs between two lists, magic and elixirs, based on a given threshold. The process involves pairing elements from magic with elixirs such that their product is at least as large as the threshold. Here is a concise overview of the method used:

• First, the function creates a list of tuples indexedMagic where each tuple consists of a spell and its corresponding index from the magic list. This enables tracking the original position of spells after sorting.
• Both the indexedMagic and the elixirs list are sorted. Sorting helps in efficiently finding the count of successful elixir pairs for each spell using a reverse search mechanism.
• A list result initialized with zeros is prepared to store the count of successful pairs for each spell index.
• The function uses a while loop inside a for loop to count and store successful pairs:
  • Loop over each spell in indexedMagic and for each spell, check in reverse from the last elixir in the sorted list elixirs (starting from the end and moving backwards) whether the product of the spell and the elixir meets or exceeds the threshold.
  • Manipulate lastValid, the marker for valid elixirs, to count the number of elixirs that, when multiplied by the current spell, meet or exceed the threshold value.
  • The count of valid elixirs for the current spell is then stored in the result list at the index corresponding to the original position of the spell.
• The final result list, which now contains the count of valid pairs per spell according to the original order of spells in magic, is returned.

This approach improves performance by reducing the number of comparisons required through sorted lists and by optimizing the search for valid pairs using the reverse search mechanism.