#2144

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Cost of Buying Candies With Discount

Minimize the total cost of buying candies using a greedy approach with a discount system based on candy prices.

Problem Statement

A store is offering a discount on candies: for every two candies you purchase, you can choose a third candy to receive for free. The free candy must be the least expensive of the three candies bought. Your goal is to determine the minimum total cost to purchase all candies.

You are given an array 'cost' where cost[i] represents the price of the ith candy. The task is to return the minimum total cost of buying all the candies under the given discount rule.

Examples

Example 1

Input: cost = [1,2,3]

Output: 5

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

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

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

Solution Approach

Greedy Approach

The key to solving this problem is to use a greedy approach. First, sort the array of candy prices in descending order. Then, for every group of three candies, you pay for the two most expensive candies and get the least expensive one for free. This ensures that you minimize the total cost by maximizing the discount on the least costly candy.

Sorting

Sorting the prices in descending order ensures that the least expensive candy (which will be free) is always the one with the smallest price in every group of three. This is a critical step because it guarantees that we always get the highest possible discount.

Edge Cases

If the number of candies is less than three, no free candy can be taken, and you must pay for all of them. Additionally, if there are exactly two candies, both need to be bought without any discount.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(n log n) due to the sorting step, where n is the number of candies. The space complexity is O(1) if sorting is done in-place, or O(n) if additional storage is required for the sorted array.

What Interviewers Usually Probe

The candidate should recognize the greedy approach to minimize the total cost by selecting the least expensive candy for free.
The candidate should explain how sorting the array affects the strategy and ensures the discount maximizes the total savings.
The candidate should be aware of edge cases like fewer than three candies and explain how the solution handles them.

Common Pitfalls or Variants

Common pitfalls

Not sorting the array before processing candies will lead to incorrect results, as the cheapest candy may not be the one chosen for the discount.
Failing to handle edge cases, such as when there are fewer than three candies, can cause errors in the solution.
Overcomplicating the solution by trying to find the best combination of candies without using a greedy approach.

Follow-up variants

Change the candy count or price range to see how the approach scales with different inputs.
Introduce multiple discount strategies, such as giving a discount after every 4th candy or offering a fixed discount on each candy.
Allow the customer to choose any candy for free, not necessarily the least expensive, to create a new variant of the problem.

FAQ

What is the pattern used to solve the Minimum Cost of Buying Candies With Discount?

The pattern used is greedy choice combined with invariant validation. You sort the candy prices and always take the least expensive candy for free in every group of three.

How do I handle the case when there are fewer than three candies?

If there are fewer than three candies, no candy can be taken for free. You must buy all the candies.

Why do we sort the candy prices in descending order?

Sorting the prices in descending order ensures that the least expensive candy in each group of three is the one you get for free, maximizing the discount.

Can the solution be optimized beyond sorting?

The solution primarily relies on sorting, which is optimal for this problem. Other optimizations would be unlikely to improve performance significantly.

What is the time complexity of this solution?

The time complexity is O(n log n) due to the sorting step, where n is the number of candies.

terminal

Solution

Solution 1: 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.

1

2

3

4

class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        cost.sort(reverse=True)
        return sum(cost) - sum(cost[2::3])

Continue Practicing

#2141 maximum running time of n computers #2136 earliest possible day of full bloom #2126 destroying asteroids