Problem Statement in English

You’re given a 0-indexed integer array cost where cost[i] is the cost of the i-th candy. The store sells a discount on the purchase of candies in the following way:

  • If you buy 2 candies, you will get a third candy for free.
  • The free candy must be of equal or lesser value than the minimum cost of the two candies you bought.

Return the minimum cost of buying all the candies.

Approach

You can solve this problem using a greedy approach. The idea is to sort the cost array in descending order and then iterate through the sorted array, adding the cost of every candy except for every third candy (which will be free).

And we’re done!

Solution in Python


class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        res = 0
        n = len(cost)

        if n <= 2:
            return sum(cost)

        cost.sort()

        paid = n - 1

        while paid > -1:
            for _ in range(2):
                if paid > -1:
                    res += cost[paid]
                    paid -= 1

            paid -= 1

        return res

Complexity

  • Time: $O(n \log n)$
    Since we are sorting the cost array, the time complexity is $O(n \log n)$.

  • Space: $O(1)$
    Since we are sorting the cost array in-place, we are not using any extra space.

And we are done.