arcbjorn

thoughtbook

Thursday, February 23, 2023

Maximum tastiness of a candy basket

Leetcode 2517 problem.

Python

  • Time complexity: O(nlog(n))O(n * log(n)) - n is a length of an array
  • Auxiliary space: O(1)O(1) - constant amount of space
class Solution:
    def maximumTastiness(self, price: List[int], k: int) -> int:
        price.sort()
        low, high = 0, sum(price)
        
        def isValidQuantity(value):
            candiesNumber = 1
            cheapest = price[0]

            for i in range(1, len(price)):
                if price[i] - cheapest >= value:
                    candiesNumber += 1
                    cheapest = price[i]

            return candiesNumber >= k

        
        while low <= high:
            mid = low + (high - low) // 2

            if isValidQuantity(mid):
                low = mid + 1
            else:
                high = mid - 1

        return high
Creative Commons Licence