Minimum Cost of Buying Candies With Discount

Easy

#1953Time: O(N log N), where N is the number of candies. This is dominated by the sorting step. The subsequent loop runs in O(N) time.Space: O(log N) or O(N) depending on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitive types uses a dual-pivot Quicksort, which requires O(log N) space for the recursion stack on average.2 companies

Patterns

Algorithms

Data structures

Companies

Prompt

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 i^th 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

Approaches

2 approaches with complexity analysis and trade-offs.

The core idea is that to minimize the total cost, we should try to get the most expensive candies for free. The discount rule allows us to get a third candy for free if its cost is less than or equal to the minimum of the two purchased candies. By sorting the candies by cost, we can devise a greedy strategy. We should buy the two most expensive candies available, which allows us to get the third most expensive one for free. This pattern is repeated for all candies.

Algorithm

Sort the cost array in non-decreasing order.
Initialize a variable totalCost to 0.
Iterate through the sorted array from right to left (from the most expensive candy to the cheapest) with a step of 3.
In each step, we are considering a group of up to three candies.
Add the cost of the most expensive candy in the group (cost[i]) to totalCost.
If a second candy exists in the group (cost[i-1]), add its cost to totalCost as well.
The third candy (cost[i-2]) is considered free and is skipped.
Continue until all candies are processed.
Return totalCost.

Walkthrough

This approach is based on a greedy strategy. The intuition is that to minimize the total cost, we should maximize the value of the candies we get for free. The most valuable free candies we can get are the most expensive ones.

Let's prove this greedy choice. Suppose we have the candies sorted by cost: c_1, c_2, ..., c_n. If we buy the two most expensive candies, c_n and c_{n-1}, we can get any candy with cost at most min(c_n, c_{n-1}) = c_{n-1} for free. To maximize our savings, we should choose the most expensive available candy that satisfies this, which is c_{n-2}. This forms a group of three: (c_n, c_{n-1}, c_{n-2}), where we pay for the first two and get the third free.

We can apply this logic repeatedly. We sort the cost array in ascending order and iterate from the end. We add the costs of the two most expensive candies to our total, then skip the third one (as it's free), and continue this process until all candies are accounted for.

1import java.util.Arrays;2 3class Solution {4    public int minimumCost(int[] cost) {5        // Sort the array in ascending order6        Arrays.sort(cost);7        8        int totalCost = 0;9        int n = cost.length;10        11        // Iterate from the most expensive candy, taking groups of three12        for (int i = n - 1; i >= 0; i -= 3) {13            // Buy the most expensive candy in the group14            totalCost += cost[i];15            // Buy the second most expensive, if it exists16            if (i - 1 >= 0) {17                totalCost += cost[i - 1];18            }19            // The third one (at i-2) is free, so we skip it by decrementing i by 320        }21        22        return totalCost;23    }24}

Complexity

Time

O(N log N), where N is the number of candies. This is dominated by the sorting step. The subsequent loop runs in O(N) time.

Space

O(log N) or O(N) depending on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitive types uses a dual-pivot Quicksort, which requires O(log N) space for the recursion stack on average.

Trade-offs

Pros

Simple to understand and implement.
Works for any range of costs, not just the constrained [1, 100].

Cons

The O(N log N) time complexity from sorting is not optimal for the given constraints where a linear time solution is possible.

This approach also uses the same greedy strategy as the first one: buy the two most expensive candies and get the third one free. However, it optimizes the sorting step. Since the costs of candies are limited to a small range [1, 100], we can use a non-comparison-based sorting algorithm like Counting Sort. This allows us to effectively sort the candies and calculate the minimum cost in linear time.

Algorithm

Create a frequency array counts of size 101, initialized to zeros.
Iterate through the input cost array. For each cost c, increment counts[c].
Initialize totalCost = 0 and a counter paidCandiesCounter = 0.
Iterate from c = 100 down to 1.
For each cost c, process all counts[c] candies of this cost:
- If paidCandiesCounter is 2, it means we have already paid for two candies, so this one is free. Reset paidCandiesCounter to 0.
- Otherwise, we must buy this candy. Add its cost c to totalCost and increment paidCandiesCounter.
Return totalCost.

Walkthrough

Given that the candy costs are within a fixed, small range (1 to 100), we can avoid the O(N log N) complexity of comparison-based sorting. A counting sort is ideal here.

First, we create a frequency array, say counts, of size 101 (for costs 0 to 100). We iterate through the input cost array and populate the frequency array: counts[c] will store the number of candies with cost c.

Then, we iterate through the frequency array from the highest cost (100) down to 1. This is equivalent to iterating through the sorted list of candies in descending order. We apply the same greedy logic: buy two, get one free. We use a counter to track our position within a group of three. For each cost c, we process all counts[c] candies. If a candy is the first or second in a group, we add its cost to the total. If it's the third, we skip it.

1class Solution {2    public int minimumCost(int[] cost) {3        // Frequency array for costs 1 to 1004        int[] counts = new int[101];5        for (int c : cost) {6            counts[c]++;7        }8        9        int totalCost = 0;10        int paidCandiesCounter = 0; // Counts paid candies in a group of 311        12        // Iterate from the most expensive cost down to the cheapest13        for (int c = 100; c >= 1; c--) {14            int numCandiesOfCostC = counts[c];15            16            for (int i = 0; i < numCandiesOfCostC; i++) {17                if (paidCandiesCounter == 2) {18                    // We have paid for 2, this one is free19                    paidCandiesCounter = 0; // Reset for the next group20                } else {21                    // Pay for this candy22                    totalCost += c;23                    paidCandiesCounter++;24                }25            }26        }27        28        return totalCost;29    }30}

Complexity

Time

O(N + M), where N is the number of candies and M is the range of possible costs (101 in this case). Creating the frequency map takes O(N). Iterating through the frequency map takes O(M + N) because the outer loop runs M times and the total number of inner loop iterations is N. This simplifies to linear time.

Space

O(M), where M is the range of costs (101 in this case). Since M is a constant based on the problem constraints, this is considered O(1) constant space.

Trade-offs

Pros

Highly efficient with a linear time complexity, which is optimal.
Constant space complexity as the size of the frequency array is fixed by the problem constraints.

Cons

This approach is only efficient because the costs are constrained to a small range. If the costs could be very large, this method would be impractical due to the large size of the frequency array.

Solutions

Solution

1class Solution {2public3  int minimumCost(int[] cost) {4    Arrays.sort(cost);5    int ans = 0;6    for (int i = cost.length - 1; i >= 0; i -= 3) {7      ans += cost[i];8      if (i > 0) {9        ans += cost[i - 1];10      }11    }12    return ans;13  }14}

1class Solution {2public:3  int minimumCost(vector<int> &cost) {4    sort(cost.rbegin(), cost.rend());5    int ans = 0;6    for (int i = 0; i < cost.size(); i += 3) {7      ans += cost[i];8      if (i < cost.size() - 1) {9        ans += cost[i + 1];10      }11    }12    return ans;13  }14};

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem