2300. Successful Pairs of Spells and Potions

Medium
Description

給定 spells 和 potions 兩個陣列以及一個整數 success。當 spells[i] * potions[j] >= success 時為成功配對。回傳每個 spell 的成功配對數量。

Example:

Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7 Output: [4,0,3]

Intuition#

排序 potions 後，對每個 spell 二分搜尋找到最小的 potion 使乘積 >= success。

  • 對每個 spell，需要找 potion >= ceil(success / spell) 的數量
  • 先排序 potions，再用二分搜尋找 lower bound

Approaches#

1: Brute Force#

  • 概念: 對每個 spell，遍歷所有 potions 計算成功配對數
  • 時間複雜度: O(m * n)（m = spells 長度，n = potions 長度）
  • 空間複雜度: O(m)（結果陣列）
Brute Force 程式碼
class Solution {
    fun successfulPairs(spells: IntArray, potions: IntArray, success: Long): IntArray {
        return IntArray(spells.size) { i ->
            potions.count { p -> spells[i].toLong() * p >= success }
        }
    }
}

⭐2: Sort + Binary Search#

  • 概念: 排序 potions，對每個 spell 二分搜尋第一個使乘積 >= success 的 potion 位置
  • 時間複雜度: O((m + n) * log n)
  • 空間複雜度: O(m)（結果陣列，不計排序空間）
class Solution {
    fun successfulPairs(spells: IntArray, potions: IntArray, success: Long): IntArray {
        potions.sort()
        val n = potions.size
        return IntArray(spells.size) { i ->
            val spell = spells[i].toLong()
            // 找第一個 potion 使得 spell * potion >= success
            var left = 0
            var right = n
            while (left < right) {
                val mid = left + (right - left) / 2
                if (spell * potions[mid] >= success) {
                    right = mid
                } else {
                    left = mid + 1
                }
            }
            n - left  // left 之後的所有 potion 都可以成功配對
        }
    }
}

注意使用 Long 避免 spell * potion 溢位。n - left 就是從 left 位置到末尾的元素個數，即成功配對數。

🔑 Takeaways#

  • Pattern: 排序 + 二分搜尋（Lower Bound）
  • 關鍵技巧: 先排序其中一個陣列，再對另一個陣列的每個元素做二分搜尋。找到分界點後，用陣列長度減去索引即為符合條件的數量