Minimum Cost of Buying Candies With Discount

Difficulty: Easy | Acceptance: 62.80% | Paid: No Topics: Array, Greedy, Sorting

A shop is selling candies. Each candy has a price given by the array cost where cost[i] is the price of the ith candy.

The shop offers a discount if you buy two candies at the same time. Specifically, if you buy two candies, you can get the third candy for free (the third candy must be one of the cheapest among the three candies you bought).

Return the minimum cost to buy all the candies.

• Examples
• Constraints
• Approach 1: Sorting (Greedy)
• Approach 2: Counting Sort (Frequency Array)

Examples

Example 1:

Input: cost = [1,2,3]
Output: 5
Explanation: We buy the candies with costs 2 and 3, and get the candy with cost 1 for free. The minimum cost is 5.

Example 2:

Input: cost = [6,5,7,9,2,2]
Output: 23
Explanation: We buy the candies with costs 9, 7, and 5, and get the candy with cost 6 for free. Then we buy the candies with costs 2 and 2, and get the candy with cost 2 for free. The minimum cost is 23.

Example 3:

Input: cost = [5,5]
Output: 10
Explanation: Since there are only 2 candies, we buy both of them. There is no discount applicable. The minimum cost is 10.

Constraints

1 <= cost.length <= 100
1 <= cost[i] <= 100

Sorting (Greedy)

Intuition To minimize the total cost, we want the free candies to be as expensive as possible. By sorting the costs in descending order, we can group the most expensive candies together. In every group of three, the smallest one (which is the last one in the sorted triplet) is free, ensuring we pay for the two most expensive ones in that group.

Steps

• Sort the array of costs in descending order.
• Iterate through the sorted array.
• For every candy at index i, if (i + 1) % 3 != 0 (meaning it’s the 1st or 2nd in a group of 3), add its cost to the total.
• Return the total.

class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        cost.sort(reverse=True)
        total = 0
        for i, c in enumerate(cost):
            if i % 3 != 2:
                total += c
        return total

Complexity

• Time: O(n log n) due to sorting.
• Space: O(1) or O(n) depending on the sorting algorithm’s space complexity.
• Notes: This is the most straightforward approach and is efficient enough given the constraints.

Counting Sort (Frequency Array)

Intuition Since the cost of a candy is limited to a maximum of 100, we can use a frequency array (counting sort) to avoid the O(n log n) sorting overhead. We iterate from the highest cost down to the lowest, simulating the purchase process.

Steps

• Initialize a frequency array of size 101 with zeros.
• Populate the frequency array by counting occurrences of each cost.
• Iterate from cost 100 down to 1.
• For each cost, while there are candies available at that price, simulate buying them. Keep a counter of candies processed. If the counter is not a multiple of 3 (i.e., not the 3rd candy), add the cost to the total.
• Return the total.

class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        freq = [0] * 101
        for c in cost:
            freq[c] += 1
        
        total = 0
        count = 0
        for i in range(100, 0, -1):
            while freq[i] > 0:
                if count % 3 != 2:
                    total += i
                count += 1
                freq[i] -= 1
        return total

Complexity

• Time: O(n + k) where n is the number of candies and k is the range of costs (100). This simplifies to O(n).
• Space: O(k) for the frequency array, which is O(1) since k is constant (101).
• Notes: This approach is theoretically faster than sorting for large n, though for n <= 100, the difference is negligible.