2144. Minimum Cost of Buying Candies With Discount

Problem Description

A shop has a special discount offer for candies. When you buy two candies, you get a third candy for free. However, there's a rule for the free candy: its cost must be less than or equal to the cheaper of the two candies you bought.

Given an array cost where cost[i] represents the price of the i-th candy, you need to find the minimum total cost to buy all the candies in the shop.

For example, if you have 4 candies with costs [1, 2, 3, 4]:

If you buy candies costing 2 and 3, the minimum of these is 2
You can take any candy costing ≤ 2 for free
So you could take the candy costing 1 for free, but not the one costing 4

The strategy involves buying candies in groups where possible to maximize the value of free candies. The solution sorts the candies by price in descending order, then groups them in sets of three. For each group of three candies, you pay for the two most expensive ones and get the third (cheapest in that group) for free.

The code sum(cost) - sum(cost[2::3]) calculates the total by:

Starting with the sum of all candy costs
Subtracting every third candy (starting from index 2) which represents the free candies in each group of three

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is that we want to maximize the value of the candies we get for free. Since we get one free candy for every two we buy, and the free candy must cost less than or equal to the minimum of the two bought candies, we should strategically choose which candies to buy together.

Think about it this way: if we're going to get free candies anyway, we want those free candies to be as expensive as possible. How do we achieve this? By pairing expensive candies together when buying, so that the "minimum of the two bought" is still relatively high.

If we sort all candies in descending order by price, we can group them in sets of three: [most expensive, second most expensive, third most expensive]. When we buy the two most expensive candies in each group, we can take the third one for free (since it's guaranteed to be ≤ the minimum of the first two).

For example, with costs [6, 5, 4, 3, 2, 1]:

Group 1: Buy 6 and 5, get 4 free (since 4 ≤ min(6,5) = 5)
Group 2: Buy 3 and 2, get 1 free (since 1 ≤ min(3,2) = 2)

This greedy approach ensures we're always getting the most expensive possible candies for free. The pattern that emerges is: after sorting in descending order, every third candy (at indices 2, 5, 8, ...) becomes free. That's why the solution subtracts sum(cost[2::3]) from the total sum - these are exactly the candies we get for free.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a greedy algorithm that maximizes the value of free candies:

Step 1: Sort the candies by price in descending order

cost.sort(reverse=True)

This ensures that when we group candies, the most expensive ones are processed first. Sorting in descending order allows us to pair high-value candies together.

Step 2: Calculate the minimum cost

return sum(cost) - sum(cost[2::3])

This line does two things:

sum(cost) calculates the total cost if we were to buy all candies without any discount
sum(cost[2::3]) calculates the sum of every third candy starting from index 2 (indices 2, 5, 8, 11, ...)
The difference gives us the actual amount we need to pay

Why this works: After sorting in descending order, the candies are arranged like: [c0, c1, c2, c3, c4, c5, ...]

When grouped in sets of three:

Group 1: [c0, c1, c2] → Buy c0 and c1, get c2 free
Group 2: [c3, c4, c5] → Buy c3 and c4, get c5 free
And so on...

The slice cost[2::3] captures exactly these free candies (c2, c5, c8, ...). Since c2 ≤ c1 ≤ c0, the condition that the free candy must cost ≤ min(bought candies) is automatically satisfied.

Time Complexity: O(n log n) due to sorting, where n is the number of candies Space Complexity: O(1) if we don't count the space used for sorting

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example with candies costing [6, 1, 3, 4, 2, 5].

Step 1: Sort in descending order After sorting: [6, 5, 4, 3, 2, 1]

Step 2: Group candies in sets of three

Group 1: [6, 5, 4]
Group 2: [3, 2, 1]

Step 3: Apply the discount strategy

For Group 1 [6, 5, 4]:

Buy candies costing 6 and 5 (pay: 6 + 5 = 11)
The minimum of the two bought is min(6, 5) = 5
We can take any candy costing ≤ 5 for free
Take the candy costing 4 for free (4 ≤ 5 ✓)

For Group 2 [3, 2, 1]:

Buy candies costing 3 and 2 (pay: 3 + 2 = 5)
The minimum of the two bought is min(3, 2) = 2
We can take any candy costing ≤ 2 for free
Take the candy costing 1 for free (1 ≤ 2 ✓)

Step 4: Calculate total cost

Total paid: 11 + 5 = 16
Free candies: 4 + 1 = 5

Using the formula:

Sum of all candies: 6 + 5 + 4 + 3 + 2 + 1 = 21
Sum of free candies (indices 2, 5 in sorted array): 4 + 1 = 5
Minimum cost: 21 - 5 = 16

The slicing cost[2::3] gives us [4, 1] which are exactly the candies at positions 2 and 5 (0-indexed) that we get for free.

Solution Implementation

1class Solution:
2    def minimumCost(self, cost: List[int]) -> int:
3        # Sort the array in descending order to prioritize buying expensive items first
4        cost.sort(reverse=True)
5      
6        # Calculate total cost minus every third item (which is free)
7        # cost[2::3] gets every third item starting from index 2 (0-indexed)
8        # This implements the "buy 2 get 1 free" offer optimally
9        total_cost = sum(cost) - sum(cost[2::3])
10      
11        return total_cost
12

1class Solution {
2    /**
3     * Calculates the minimum cost to buy all items with a "buy 2 get 1 free" offer.
4     * The strategy is to buy the most expensive items first and get the cheapest ones free.
5     * 
6     * @param cost Array containing the cost of each item
7     * @return The minimum total cost to buy all items
8     */
9    public int minimumCost(int[] cost) {
10        // Sort the array in ascending order to process from most expensive items
11        Arrays.sort(cost);
12      
13        // Initialize total cost accumulator
14        int totalCost = 0;
15      
16        // Process items in groups of 3, starting from the most expensive
17        // Buy the two most expensive items in each group, get the third one free
18        for (int i = cost.length - 1; i >= 0; i -= 3) {
19            // Add the most expensive item in the current group
20            totalCost += cost[i];
21          
22            // Add the second most expensive item if it exists
23            if (i > 0) {
24                totalCost += cost[i - 1];
25            }
26            // The third item (at index i-2) is free, so we skip it
27        }
28      
29        return totalCost;
30    }
31}
32

1class Solution {
2public:
3    int minimumCost(vector<int>& cost) {
4        // Sort the array in descending order to prioritize buying expensive items first
5        sort(cost.rbegin(), cost.rend());
6      
7        int totalCost = 0;
8      
9        // Process items in groups of 3
10        // Buy 2 items and get the 3rd one free (skip every 3rd item)
11        for (int i = 0; i < cost.size(); i += 3) {
12            // Add the first item in the group
13            totalCost += cost[i];
14          
15            // Add the second item if it exists
16            if (i + 1 < cost.size()) {
17                totalCost += cost[i + 1];
18            }
19            // The third item (i + 2) is free, so we skip it
20        }
21      
22        return totalCost;
23    }
24};
25

1/**
2 * Calculates the minimum cost when buying items with a "buy 2 get 1 free" promotion.
3 * The strategy is to group items in sets of 3, where the cheapest item in each group is free.
4 * 
5 * @param cost - Array of item costs
6 * @returns The minimum total cost after applying the promotion
7 */
8function minimumCost(cost: number[]): number {
9    // Sort the costs in ascending order
10    cost.sort((a: number, b: number) => a - b);
11  
12    // Initialize the total cost accumulator
13    let totalCost: number = 0;
14  
15    // Iterate from the most expensive item, moving backwards by 3 items at a time
16    // This ensures we get the most expensive items while making the cheapest ones free
17    for (let i: number = cost.length - 1; i >= 0; i -= 3) {
18        // Add the most expensive item in the current group of 3
19        totalCost += cost[i];
20      
21        // Add the second most expensive item if it exists
22        // The third item (cheapest) in the group is free
23        if (i > 0) {
24            totalCost += cost[i - 1];
25        }
26    }
27  
28    return totalCost;
29}
30

Time and Space Complexity

The time complexity is O(n log n), where n is the length of the cost array. This is dominated by the sorting operation cost.sort(reverse=True), which uses Timsort algorithm with O(n log n) worst-case complexity. The subsequent operations sum(cost) and sum(cost[2::3]) both have O(n) time complexity, but these are overshadowed by the sorting step.

The space complexity is O(log n). While the sorting is done in-place and doesn't require additional space proportional to the input size, the Timsort algorithm uses O(log n) space for its internal stack during the sorting process to keep track of merge operations. The slicing operation cost[2::3] creates a new list, but this contains at most n/3 elements, which is O(n). However, considering only the auxiliary space used by the sorting algorithm itself (not counting the space for the output of intermediate operations), the space complexity is O(log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Sort or Sorting in Wrong Order

A critical mistake is either forgetting to sort the array or sorting it in ascending order instead of descending order. This completely breaks the greedy strategy.

Incorrect approach:

def minimumCost(self, cost: List[int]) -> int:
    # Wrong: No sorting or ascending sort
    cost.sort()  # Ascending order
    return sum(cost) - sum(cost[2::3])

Why it fails: With ascending sort, you'd group cheap candies together and get even cheaper ones free, missing the opportunity to get expensive candies for free.

Example: For cost = [1, 2, 3, 4, 5, 6]

Wrong (ascending): Groups as [1,2,3], [4,5,6] → Pay for 1,2,4,5 = 12
Correct (descending): Groups as [6,5,4], [3,2,1] → Pay for 6,5,3,2 = 16 (Wait, this seems wrong!)

Actually, let me recalculate:

Ascending: Free candies are 3 and 6 → Pay 1+2+4+5 = 12
Descending: Free candies are 4 and 1 → Pay 6+5+3+2 = 16

The descending order gives us the optimal result because we get more valuable items (4 vs 3) for free overall.

2. Misunderstanding the Slicing Syntax

Using incorrect slice notation like cost[3::3] instead of cost[2::3].

Incorrect approach:

def minimumCost(self, cost: List[int]) -> int:
    cost.sort(reverse=True)
    return sum(cost) - sum(cost[3::3])  # Wrong starting index!

Why it fails: cost[3::3] starts from index 3 (the 4th element), missing the pattern of every third candy being free. Remember that in groups of three, the third candy (index 2, 5, 8...) is free.

3. Not Handling Edge Cases

Failing to consider arrays with fewer than 3 elements.

The good news: The given solution actually handles these cases correctly!

For 1 candy: cost[2::3] returns empty list, sum is 0, so we pay full price
For 2 candies: Same as above, we pay for both
This aligns with the problem logic - you need to buy 2 to get 1 free

4. Modifying Original Array Without Consideration

If the problem requires preserving the original array order (for other operations), sorting in-place could cause issues.

Solution if preservation needed:

def minimumCost(self, cost: List[int]) -> int:
    sorted_cost = sorted(cost, reverse=True)  # Creates a new sorted list
    return sum(sorted_cost) - sum(sorted_cost[2::3])

5. Integer Overflow in Other Languages

While not an issue in Python, implementing this in languages like C++ or Java requires attention to potential integer overflow when summing large arrays.

Solution for other languages: Use appropriate data types (e.g., long long in C++ or long in Java) for accumulating sums.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What does the following code do?

1def f(arr1, arr2):
2  i, j = 0, 0
3  new_arr = []
4  while i < len(arr1) and j < len(arr2):
5      if arr1[i] < arr2[j]:
6          new_arr.append(arr1[i])
7          i += 1
8      else:
9          new_arr.append(arr2[j])
10          j += 1
11  new_arr.extend(arr1[i:])
12  new_arr.extend(arr2[j:])
13  return new_arr
14

1public static List<Integer> f(int[] arr1, int[] arr2) {
2  int i = 0, j = 0;
3  List<Integer> newArr = new ArrayList<>();
4
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.add(arr1[i]);
8          i++;
9      } else {
10          newArr.add(arr2[j]);
11          j++;
12      }
13  }
14
15  while (i < arr1.length) {
16      newArr.add(arr1[i]);
17      i++;
18  }
19
20  while (j < arr2.length) {
21      newArr.add(arr2[j]);
22      j++;
23  }
24
25  return newArr;
26}
27

1function f(arr1, arr2) {
2  let i = 0, j = 0;
3  let newArr = [];
4  
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.push(arr1[i]);
8          i++;
9      } else {
10          newArr.push(arr2[j]);
11          j++;
12      }
13  }
14  
15  while (i < arr1.length) {
16      newArr.push(arr1[i]);
17      i++;
18  }
19  
20  while (j < arr2.length) {
21      newArr.push(arr2[j]);
22      j++;
23  }
24  
25  return newArr;
26}
27

Find the intersection of two arrays.

Check if one array is a subsequence of the other.

Merge two sorted arrays.

Finding median values of 2 arrays.

I don't know