A shop is selling candies at a discount. For every two candies sold, the shop gives a third candy for free.
The customer can choose any candy to take away for free as long as the cost of the chosen candy is less than or equal to the minimum cost of the two candies bought.
4 candies with costs 1, 2, 3, and 4, and the customer buys candies with costs 2 and 3, they can take the candy with cost 1 for free, but not the candy with cost 4.Given a 0-indexed integer array cost, where cost[i] denotes the cost of the ith candy, return the minimum cost of buying all the candies.
Example 1:
Input: cost = [1,2,3] Output: 5 Explanation: We buy the candies with costs 2 and 3, and take the candy with cost 1 for free. The total cost of buying all candies is 2 + 3 = 5. This is the only way we can buy the candies. Note that we cannot buy candies with costs 1 and 3, and then take the candy with cost 2 for free. The cost of the free candy has to be less than or equal to the minimum cost of the purchased candies.
Example 2:
Input: cost = [6,5,7,9,2,2] Output: 23 Explanation: The way in which we can get the minimum cost is described below: - Buy candies with costs 9 and 7 - Take the candy with cost 6 for free - We buy candies with costs 5 and 2 - Take the last remaining candy with cost 2 for free Hence, the minimum cost to buy all candies is 9 + 7 + 5 + 2 = 23.
Example 3:
Input: cost = [5,5] Output: 10 Explanation: Since there are only 2 candies, we buy both of them. There is not a third candy we can take for free. Hence, the minimum cost to buy all candies is 5 + 5 = 10.
Constraints:
1 <= cost.length <= 1001 <= cost[i] <= 100Problem Overview: You are given an array where cost[i] represents the price of the i-th candy. A store offers a discount: for every two candies you buy, you can get a third candy for free, as long as its price is less than or equal to the cheaper of the two. The goal is to minimize the total amount you pay.
Approach 1: Sort and Pick Strategy (Greedy + Sorting) (Time: O(n log n), Space: O(1) extra)
The key insight is that you want the most expensive candies counted as paid items while making cheaper candies the free ones. Sort the array in descending order using a sorting step. Then iterate through the array and simulate buying candies in groups of three: pay for the first two, skip the third because it becomes free. Since the list is sorted from highest to lowest, the skipped candy will always be the cheapest among the group, satisfying the discount condition. This greedy ordering guarantees the lowest total payment while keeping the implementation simple.
Approach 2: Two-Pointers from End (Greedy Scan) (Time: O(n log n), Space: O(1))
This variation also relies on sorting but uses pointer movement to process purchases more explicitly. First sort the array in ascending order. Use a pointer starting from the most expensive candy at the end of the array. Each step simulates buying two candies by adding their prices to the total, then moving the pointer one more position to skip the next candy as the free one. The pointer effectively walks backward across the array in blocks of three. The logic reflects the same greedy idea: expensive candies should be paid, while cheaper ones become the discounted items.
Both strategies rely on ordering the array and then grouping candies so the lowest value in each triple becomes free. The main operations are sorting and linear iteration over the array.
Recommended for interviews: The Sort and Pick greedy approach is what interviewers usually expect. It shows you recognized the optimal greedy ordering and reduced the problem to sorting plus a simple scan. The two-pointer variation communicates the same idea but makes the purchase simulation more explicit.
This approach involves sorting the array in descending order. By doing so, you're prioritizing the selection of the most expensive candies you need to pay for, maximizing chance taking cheaper candies for free subsequently. Iterate over the sorted array in steps of 3, only summing the cost of the first two in every trio step.
The function sorts the array in descending order and adds every first and second element in a window of three items to calculate the minimum cost. We leverage qsort to efficiently handle the sorting.
Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(1) as the sorting is done in-place and only a few extra variables are used.
This strategy utilizes a two-pointer mechanism starting from both ends of the sorted array. It focuses on ensuring that every possible free candy is paired with the costliest ones remaining.
This solution sorts the array in ascending order and processes from the end backwards, skipping every third element in grouping, making the deduction calculations for the free item simpler by naturally passing them by iteration.
Time Complexity: O(n log n) because of the sort operation.
Space Complexity: O(1) with in-place alterations and computation.
We can first sort the candies by price in descending order, then for every three candies, we take two. This ensures that the candies we get for free are the most expensive, thereby minimizing the total cost.
The time complexity is O(n log n), and the space complexity is O(log n). Here, n is the number of candies.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Sort and Pick Strategy | Time Complexity: O(n log n) due to the sorting operation. |
| Approach 2: Two-Pointers from End | Time Complexity: O(n log n) because of the sort operation. |
| Greedy Algorithm | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Pick Strategy | O(n log n) | O(1) | General case; simplest greedy implementation after sorting |
| Two-Pointers from End | O(n log n) | O(1) | When you want explicit control of grouping purchases using pointer traversal |
2144 Minimum Cost of Buying Candies With Discount | LeetCode 2144 || BiWeekly- 70 || Greedy • Bro Coders • 1,438 views views
Watch 9 more video solutions →Practice Minimum Cost of Buying Candies With Discount with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor