Minimum Cost of Buying Candies With Discount solution and explanation
Nokia
9 more videos on this problem
Minimum Cost of Buying Candies With Discount | Simple Intuition | Leetcode 2144 | codestorywithMIKcodestorywithMIK · 13:21 · 4K views
2144 Minimum Cost of Buying Candies With Discount | LeetCode 2144 || BiWeekly- 70 || GreedyBro Coders · 5:23 · 1K views
Minimum Cost of Buying Candies With Discount | Leetcode 2144 | BI-Weekly Contest 70 Solution | JavaPepcoding · 7:01 · 1K views
2144. Minimum Cost of Buying Candies With Discount (Leetcode Easy)Programming Live with Larry · 3:17 · 403 views
2144. Minimum Cost of Buying Candies With Discount | Leetcode Daily - PythonLeetcode Daily · 5:30 · 315 views
Minimum Cost of Buying Candies With Discount | LeetCode 2144 | Greedy Approach ExplainedStreak To Scale · 2:56 · 166 views
LeetCode 2144 - Minimum Cost of Buying Candies With Discount - JavaScript - [EASY]NoviceJS · 7:13 · 131 views
2144 Minimum Cost of Buying Candies With DiscountLets program · 9:10 · 60 views
Leetcode 2144. Minimum Cost of Buying Candies With DiscountExpertFunda · 25:14 · 46 views
2144. Minimum Cost of Buying Candies With DiscountLogN · 8:30 · 37 views
The problem
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
4candies with costs1,2,3, and4, and the customer buys candies with costs2and3, they can take the candy with cost1for free, but not the candy with cost4.
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] <= 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.
def minimumCost(cost):
cost.sort(reverse=True)
min_cost = 0
for i in range(0, len(cost), 3):
min_cost += cost[i]
if i + 1 < len(cost):
min_cost += cost[i + 1]
return min_cost
# Example usage
cost = [6, 5, 7, 9, 2, 2]
print("Minimum cost:", minimumCost(cost))import java.util.Arrays;
public class Main {
public static int minimumCost(int[] cost) {
Arrays.sort(cost);
int n = cost.length;
int minCost = 0;
for (int i = n - 1; i >= 0; i -= 3) {
minCost += cost[i];
if (i - 1 >= 0) {
minCost += cost[i - 1];
}
}
return minCost;
}
public static void main(String[] args) {
int[] cost = {6, 5, 7, 9, 2, 2};
System.out.println("Minimum cost: " + minimumCost(cost));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minimumCost(vector<int>& cost) {
sort(cost.rbegin(), cost.rend());
int minCost = 0;
for (int i = 0; i < cost.size(); i += 3) {
minCost += cost[i];
if (i + 1 < cost.size()) {
minCost += cost[i + 1];
}
}
return minCost;
}
int main() {
vector<int> cost = {6, 5, 7, 9, 2, 2};
cout << "Minimum cost: " << minimumCost(cost) << endl;
return 0;
}function minimumCost(cost) {
cost.sort((a, b) => b - a);
let minCost = 0;
for (let i = 0; i < cost.length; i += 3) {
minCost += cost[i];
if (i + 1 < cost.length) {
minCost += cost[i + 1];
}
}
return minCost;
}
// Example usage
let cost = [6, 5, 7, 9, 2, 2];
console.log("Minimum cost:", minimumCost(cost));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)b - *(int *)a);
}
int minimumCost(int* cost, int costSize) {
qsort(cost, costSize, sizeof(int), compare);
int minCost = 0;
for (int i = 0; i < costSize; i += 3) {
minCost += cost[i];
if (i + 1 < costSize) {
minCost += cost[i + 1];
}
}
return minCost;
}
int main() {
int cost[] = {6, 5, 7, 9, 2, 2};
int size = sizeof(cost) / sizeof(cost[0]);
printf("Minimum cost: %d\n", minimumCost(cost, size));
return 0;
}using System;
using System.Linq;
class Program {
static int MinimumCost(int[] cost) {
Array.Sort(cost, (a, b) => b.CompareTo(a));
int minCost = 0;
for (int i = 0; i < cost.Length; i += 3) {
minCost += cost[i];
if (i + 1 < cost.Length) {
minCost += cost[i + 1];
}
}
return minCost;
}
static void Main() {
int[] cost = {6, 5, 7, 9, 2, 2};
Console.WriteLine("Minimum cost: " + MinimumCost(cost));
}
}The Python solution uses reverse sorting and a list comprehension-like loop approach to accommodate the indexing of each group of three candies, optimizing via in-place operations.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1), as it works on existing list structure.
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.
def minimumCost(cost):
cost.sort()
min_cost = 0
for i in range(len(cost) - 1, -1, -3):
min_cost += cost[i]
if i - 1 >= 0:
min_cost += cost[i - 1]
return min_cost
# Example usage
cost = [6, 5, 7, 9, 2, 2]
print("Minimum cost:", minimumCost(cost))import java.util.Arrays;
public class Main {
public static int minimumCost(int[] cost) {
Arrays.sort(cost);
int n = cost.length;
int minCost = 0;
for (int i = n - 1; i >= 0; i -= 3) {
minCost += cost[i];
if (i - 1 >= 0) {
minCost += cost[i - 1];
}
}
return minCost;
}
public static void main(String[] args) {
int[] cost = {6, 5, 7, 9, 2, 2};
System.out.println("Minimum cost: " + minimumCost(cost));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minimumCost(vector<int>& cost) {
sort(cost.begin(), cost.end());
int minCost = 0;
for (int i = cost.size() - 1; i >= 0; i -= 3) {
minCost += cost[i];
if (i - 1 >= 0) {
minCost += cost[i - 1];
}
}
return minCost;
}
int main() {
vector<int> cost = {6, 5, 7, 9, 2, 2};
cout << "Minimum cost: " << minimumCost(cost) << endl;
return 0;
}function minimumCost(cost) {
cost.sort((a, b) => a - b);
let minCost = 0;
for (let i = cost.length - 1; i >= 0; i -= 3) {
minCost += cost[i];
if (i - 1 >= 0) {
minCost += cost[i - 1];
}
}
return minCost;
}
// Example usage
let cost = [6, 5, 7, 9, 2, 2];
console.log("Minimum cost:", minimumCost(cost));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int minimumCost(int* cost, int costSize) {
qsort(cost, costSize, sizeof(int), compare);
int minCost = 0;
for (int i = costSize - 1; i >= 0; i -= 3) {
minCost += cost[i];
if (i - 1 >= 0) {
minCost += cost[i - 1];
}
}
return minCost;
}
int main() {
int cost[] = {6, 5, 7, 9, 2, 2};
int size = sizeof(cost) / sizeof(cost[0]);
printf("Minimum cost: %d\n", minimumCost(cost, size));
return 0;
}using System;
class Program {
static int MinimumCost(int[] cost) {
Array.Sort(cost);
int minCost = 0;
for (int i = cost.Length - 1; i >= 0; i -= 3) {
minCost += cost[i];
if (i - 1 >= 0) {
minCost += cost[i - 1];
}
}
return minCost;
}
static void Main() {
int[] cost = {6, 5, 7, 9, 2, 2};
Console.WriteLine("Minimum cost: " + MinimumCost(cost));
}
}Python dynamically interprets the similar logic with a descending step value to reach optimal final cost dynamically through sum controls and inherent reverse progress.
Time Complexity: O(n log n), employing stored efficiencies with O(1) space apart from data-holding list structures.
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.
function minimumCost(cost: number[]): number {
cost.sort((a, b) => a - b);
let ans = 0;
for (let i = cost.length - 1; i >= 0; i -= 3) {
ans += cost[i];
if (i) {
ans += cost[i - 1];
}
}
return ans;
}func minimumCost(cost []int) (ans int) {
sort.Ints(cost)
for i := len(cost) - 1; i >= 0; i -= 3 {
ans += cost[i]
if i > 0 {
ans += cost[i-1]
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sort and Pick Strategy | Time Complexity: O(n log n) due to sorting. |
| Approach 2: Two-Pointers from End | Time Complexity: O(n log n), employing stored efficiencies with O(1) space apart from data-holding list structures. |
| Greedy Algorithm | – |
Complexity analysis
| 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 |
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.