# Minimum Cost of Buying Candies With Discount
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-cost-of-buying-candies-with-discount)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-of-buying-candies-with-discount
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Garmin](https://scaleengineer.com/companies/garmin), [Nokia](https://scaleengineer.com/companies/nokia)
---
## 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 `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`

# Approaches
## Greedy Approach with Sorting
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public int minimumCost(int[] cost) {
        // Sort the array in ascending order
        Arrays.sort(cost);
        
        int totalCost = 0;
        int n = cost.length;
        
        // Iterate from the most expensive candy, taking groups of three
        for (int i = n - 1; i >= 0; i -= 3) {
            // Buy the most expensive candy in the group
            totalCost += cost[i];
            // Buy the second most expensive, if it exists
            if (i - 1 >= 0) {
                totalCost += cost[i - 1];
            }
            // The third one (at i-2) is free, so we skip it by decrementing i by 3
        }
        
        return totalCost;
    }
}
```
### 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`.

## Greedy Approach with Counting Sort
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int minimumCost(int[] cost) {
        // Frequency array for costs 1 to 100
        int[] counts = new int[101];
        for (int c : cost) {
            counts[c]++;
        }
        
        int totalCost = 0;
        int paidCandiesCounter = 0; // Counts paid candies in a group of 3
        
        // Iterate from the most expensive cost down to the cheapest
        for (int c = 100; c >= 1; c--) {
            int numCandiesOfCostC = counts[c];
            
            for (int i = 0; i < numCandiesOfCostC; i++) {
                if (paidCandiesCounter == 2) {
                    // We have paid for 2, this one is free
                    paidCandiesCounter = 0; // Reset for the next group
                } else {
                    // Pay for this candy
                    totalCost += c;
                    paidCandiesCounter++;
                }
            }
        }
        
        return totalCost;
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  int minimumCost(int[] cost) {
    Arrays.sort(cost);
    int ans = 0;
    for (int i = cost.length - 1; i >= 0; i -= 3) {
      ans += cost[i];
      if (i > 0) {
        ans += cost[i - 1];
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumCost(vector<int> &cost) {
    sort(cost.rbegin(), cost.rend());
    int ans = 0;
    for (int i = 0; i < cost.size(); i += 3) {
      ans += cost[i];
      if (i < cost.size() - 1) {
        ans += cost[i + 1];
      }
    }
    return ans;
  }
};

```

### Python

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

```