Master the Art of Spell and Potion Pairing: A TypeScript Binary Search Approach (100% / 87.50%)
Intuition\nGiven two arrays representing the strengths of spells and potions, our task is to find the number of successful pairs for each spell. A pair is consi
# Intuition\nGiven two arrays representing the strengths of spells and potions, our task is to find the number of successful pairs for each spell. A pair is considered successful if the product of the strengths of the spell and the potion is at least equal to a given `success` value. To solve this problem efficiently, we can take advantage of a binary search algorithm on the sorted potions array for each spell.\n\n# Approach\n1. **Sort the potions array:** First, we sort the potions array in ascending order. This enables us to perform binary search on the array later in the process. Sorting takes $$O(m * log(m))$$ time, where m is the length of the potions array.\n2. **Define a binary search function:** We create a binary search function that takes an array and a target value as inputs. The function iterates over the array and finds the index where the target value should be inserted while maintaining the sorted order of the array. This function has a time complexity of $$O(log(m))$$ as it is applied to the sorted potions array.\n3. **Iterate over spells:** For each spell in the spells array, we calculate the minimum potion strength required to form a successful pair. To do this, we divide the `success` value by the strength of the current spell and round up to the nearest integer. This gives us the minimum potion strength that, when multiplied by the current spell strength, will produce a product greater than or equal to the `success` value. We then use the binary search function to find the index where this minimum potion strength should be inserted in the sorted potions array.\n4. **Calculate the number of successful pairs:** The number of successful pairs for a given spell is the difference between the length of the potions array and the index found using binary search. This is because all the potions at the index and to the right of it in the sorted array have a strength greater than or equal to the minimum potion strength required for a successful pair with the current spell.\n5. **Return an array with the results:** Finally, we return an array with the number of successful pairs for each spell by mapping over the spells array and performing the above steps for each element. The returned array has the same length as the input spells array.\n\n# Complexity\nTime complexity: $$O(n\u2217log(m))$$, where n is the length of the spells array and m is the length of the potions array. This complexity is due to sorting the potions array in $$O(m * log(m))$$ time and performing binary search on the potions array for each spell in $$O(n * log(m))$$ time.\nSpace complexity: $$O(1)$$, as we only use a constant amount of additional memory for temporary variables.\n\n# Code\n```\n/**\n * Performs binary search on a sorted array to find the index where the target value should be inserted.\n * \n * @param arr - A sorted array of numbers.\n * @param target - The target number to be searched for.\n * @returns The index where the target value should be inserted to maintain the sorted order.\n */\nfunction binarySearch(arr: number[], target: number): number {\n  let left = 0;\n  let right = arr.length - 1;\n\n  // Iterate until the left and right pointers converge.\n  while (left <= right) {\n    const mid = left + Math.floor((right - left) / 2);\n\n    if (arr[mid] < target) {\n      left = mid + 1;\n    } else {\n      right = mid - 1;\n    }\n  }\n\n  // Return the index where the target value should be inserted.\n  return left;\n}\n\n/**\n * Calculates the number of successful pairs of spells and potions.\n * A spell and potion pair is considered successful if the product of their strengths is at least `success`.\n *\n * @param spells - An array of integers representing the strengths of the spells.\n * @param potions - An array of integers representing the strengths of the potions.\n * @param success - An integer representing the minimum product of spell and potion strengths required for success.\n * @returns An array of integers representing the number of potions that will form a successful pair with each spell.\n */\nfunction successfulPairs(spells: number[], potions: number[], success: number): number[] {\n  // Sort the potions list in ascending order to allow for efficient binary search.\n  potions.sort((a, b) => a - b);\n\n  // Iterate over each spell in the spells list and use binary search to find the index of the first potion\n  // that forms a successful pair, then calculate the number of successful pairs for each spell.\n  // The map function creates a new array with the results of calling the provided function on every element in the original spells array.\n  return spells.map(\n    // Calculate the minimum potion strength required to form a successful pair\n    // with the current spell, and use binary search to find the index where the target value should be inserted.\n    (spell) => potions.length - binarySearch(potions, Math.ceil(success / spell))\n  );\n}\n```\n![2300. Successful Pairs of Spells and Potions.PNG](https://assets.leetcode.com/users/images/e1438d97-4336-441e-bc1c-810381166d23_1680447034.2240133.png)\n
['Array', 'Binary Search', 'Sorting', 'TypeScript']