LC-2300 Medium LeetCode

2300. Successful Pairs of Spells and Potions

Array Two Pointers Binary Search Sorting

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 45% Topics: Array, Two Pointers, Binary Search, Sorting

Reading material

Arrays & Hashing 12 min Two Pointers 9 min Binary Search 12 min

Reference solution (spoiler · python)

# Time:  O(mlogm + nlogm)
# Space: O(1)

# binary search
class Solution(object):
    def successfulPairs(self, spells, potions, success):
        """
        :type spells: List[int]
        :type potions: List[int]
        :type success: int
        :rtype: List[int]
        """
        def ceil_divide(a, b):
            return (a+(b-1))//b
            
        potions.sort()
        return [len(potions)-bisect.bisect_left(potions, ceil_divide(success, s)) for s in spells]

Solution from kamyu104/LeetCode-Solutions · MIT