2144. Minimum Cost of Buying Candies With Discount

Array
Greedy
Sorting

TIME

O(n log n)

SPACE

O(1)

Intuition

To minimize the total payment, we want the free candies to be as expensive as possible.

Sort candy costs from highest to lowest. In each group of three, pay for the two most expensive candies and take the third candy for free. The free candy is valid because its cost is less than or equal to both candies bought before it.

Approach

Sort cost in descending order.
Iterate through the sorted costs.
Add a candy's cost to the answer unless its index is the third position in a group, where index % 3 == 2.
Return the total.

Complexity

Time: O(n log n), sorting dominates
Space: O(1) extra, ignoring sorting implementation details

Edge Cases

Fewer than three candies -> pay for all candies
Exactly three candies -> cheapest candy is free
Number of candies is not divisible by three -> remaining one or two candies must be paid for
Equal candy costs -> any valid grouping gives the same result

Code

from typing import List


class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        """
        2144. Minimum Cost of Buying Candies With Discount
        Time: O(n log n)
        Space: O(1)
        """
        cost.sort(reverse=True)

        total = 0
        for index, candy_cost in enumerate(cost):
            if index % 3 != 2:
                total += candy_cost

        return total

import java.util.Arrays;

/**
 * 2144. Minimum Cost of Buying Candies With Discount
 * Time: O(n log n)
 * Space: O(1)
 */
class Solution {
    public int minimumCost(int[] cost) {
        Arrays.sort(cost);

        int total = 0;
        int positionInGroup = 0;

        for (int index = cost.length - 1; index >= 0; index--) {
            if (positionInGroup != 2) {
                total += cost[index];
            }
            positionInGroup = (positionInGroup + 1) % 3;
        }

        return total;
    }
}