Skip to main content
Talentd

Minimum Cost of Buying Candies With Discount - Solution & Explanation

EasyArrayGreedySorting15 min readAsked at: Amazon, Meta, Nokia +2
Practice this problem

Problem Statement

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.

  • For example, if there are 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 <= 100
  • 1 <= cost[i] <= 100

Approach Overview

Problem 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 1: Approach 1: Sort and Pick Strategy

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Two-Pointers from End

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) because of the sort operation.
Space Complexity: O(1) with in-place alterations and computation.

Try this approach in the editor →

Approach 3: Greedy Algorithm

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Sort and Pick Strategy

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.

Approach 2: Two-Pointers from End

Time Complexity: O(n log n) because of the sort operation.
Space Complexity: O(1) with in-place alterations and computation.

Greedy Algorithm—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sort and Pick StrategyO(n log n)O(1)General case; simplest greedy implementation after sorting
Two-Pointers from EndO(n log n)O(1)When you want explicit control of grouping purchases using pointer traversal

Video Solution

Minimum Cost of Buying Candies With Discount | Simple Intuition | Leetcode 2144 | codestorywithMIK • codestorywithMIK • 4,481 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Cost of Buying Candies With Discount easy or hard?
LeetCode classifies this problem as Easy. The main challenge is recognizing the greedy rule: make the cheapest candy in every group of three the free one. Once the array is sorted, the rest of the solution is a straightforward linear scan.
Minimum Cost of Buying Candies With Discount Python/Java solution
In Python or Java, the solution sorts the cost array and iterates through it while skipping every third element. For example, after sorting in descending order, you add prices at indices 0 and 1, skip index 2, then continue the pattern. The implementation is short and runs in O(n log n) time.
How to solve Minimum Cost of Buying Candies With Discount in O(n)?
A pure O(n) solution is generally not used because the greedy strategy requires ordering candies by price. Sorting the array ensures the cheapest candy in each group becomes the free one. Without sorting, you cannot reliably determine which candies should be discounted, so the practical solution remains O(n log n).
What is the best approach for Minimum Cost of Buying Candies With Discount?
The optimal approach is a greedy strategy combined with sorting. Sort the candy prices in descending order and iterate through them, paying for the first two candies in every group of three and skipping the third as the free one. This ensures the cheapest candy in each group becomes the free item. The overall complexity is O(n log n) due to sorting.
Is Minimum Cost of Buying Candies With Discount asked at Google/Amazon/Meta?
This problem represents a classic greedy pattern involving sorting and grouping items. Variations of similar discount or grouping optimization problems appear in interviews at companies like Amazon and Google. The focus is typically on recognizing the greedy ordering that minimizes total cost.
What data structure is used in Minimum Cost of Buying Candies With Discount?
The primary data structure is an array that stores candy prices. The algorithm sorts the array and then performs a sequential scan or pointer traversal to group candies into sets of three. No additional complex data structures are required.
What is the time complexity of Minimum Cost of Buying Candies With Discount?
The dominant operation is sorting the price array, which takes O(n log n) time. After sorting, the algorithm performs a single linear pass through the array to accumulate the cost while skipping every third candy. The space complexity is O(1) if sorting is done in-place.

Ready to solve this problem?

Practice Minimum Cost of Buying Candies With Discount with our built-in code editor and test cases.

Practice on FleetCode
Previous

Array Partition

Next

Check if Grid Satisfies Conditions