2144. Minimum Cost of Buying Candies With Discount

Time: O(n log n)

Space: O(n)

Intuition

To minimize total payment under buy-2-get-1-free, each free candy should be as expensive as possible. Sorting in descending order and taking every third candy as free guarantees that the skipped candy in each group is the best possible free choice.

Algorithm

1Sort the cost array in descending order.
2Initialize answer = 0.
3Traverse i from 0 to n-1:
4 If i % 3 != 2, add cost[i] to answer.
5 If i % 3 == 2, skip cost[i] because it is free.
6Return answer.

Example Walkthrough

Input: cost = [6, 5, 7, 9, 2, 2]

1.Sort descending -> [9, 7, 6, 5, 2, 2].
2.Indices 0,1 paid: 9 + 7.
3.Index 2 free: 6 skipped.
4.Indices 3,4 paid: 5 + 2, index 5 free: 2 skipped.

Output: 23

Common Pitfalls

•Skipping every third element before sorting is incorrect.
•Ascending sort gives suboptimal free candies and larger total payment.
•For very large constraints in other languages, watch integer overflow in the sum.

2144.cs

// Approach: Sort costs in descending order and process candies in groups of three.
// In every group, pay for the first two (most expensive) and get the third for free to minimize total cost.
// Time: O(n log n) Space: O(n)

public class Solution
{
    public int MinimumCost(int[] cost)
    {
        int ans = 0;

        cost = cost.OrderByDescending(x => x).ToArray();

        for (int i = 0; i < cost.Length; ++i)
        {
            if (i % 3 != 2)
                ans += cost[i];
        }

        return ans;
    }
}

Was this solution helpful?