Watch 10 video solutions for Minimum Cost of Buying Candies With Discount, a easy level problem involving Array, Greedy, Sorting. This walkthrough by Bro Coders has 1,438 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |