LeetCode 2144 - Minimum Cost of Buying Candies With Discount

LeetCode Problem 2144

Difficulty: 🟢 Easy
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

This problem asks us to minimize the total amount of money spent when buying candies under a special discount rule.

For every two candies that are purchased, we may take one additional candy for free. However, the free candy must have a cost less than or equal to the cheaper of the two purchased candies.

The input is a 0-indexed integer array cost, where each value represents the price of a candy. We must acquire every candy in the array, either by paying for it or by receiving it as a free candy through the discount rule.

The goal is to compute the minimum total amount of money needed to obtain all candies.

The constraints are small:

• The array length is at most 100
• Each candy cost is between 1 and 100

These constraints mean that even relatively inefficient approaches could pass, but the problem is fundamentally a greedy optimization problem, and there is a very clean optimal strategy.

The important observation is that a free candy should be as expensive as possible, because every free candy directly reduces the amount we pay. However, the free candy must still satisfy the discount condition.

Several edge cases are important:

• Arrays with fewer than three candies cannot use the discount at all.
• Arrays whose length is not divisible by three will leave one or two candies that must always be paid for.
• Multiple candies may have the same value, so the implementation must not rely on uniqueness.
• A naive grouping strategy may fail if expensive candies are used as free candies illegally.

Approaches

Brute Force Approach

A brute force solution would try every possible way to group candies into sets of three, where two candies are purchased and one eligible candy is free.

For each grouping, we would verify whether the free candy satisfies the condition:

• free <= min(bought1, bought2)

Then we would compute the total cost paid and keep the minimum across all valid arrangements.

This works because it exhaustively explores all possible purchase combinations, guaranteeing that the optimal answer is found.

However, the number of possible groupings grows extremely quickly. Even for moderate array sizes, the number of permutations and partitions becomes enormous. Since the constraints allow up to 100 candies, brute force is completely impractical.

Optimal Greedy Approach

The key insight is that the free candy should always be the cheapest candy within a group of three expensive candies.

To maximize savings:

1. Sort the candies in descending order.
2. Process candies in groups of three.
3. For every group:

• Pay for the first two candies.
• Get the third candy for free.

Why does this work?

Suppose we have candies sorted from largest to smallest:

9, 7, 6, 5, 2, 2

If we buy 9 and 7, then 6 can legally be free because:

6 <= min(9, 7)

Since 6 is the third largest candy, making it free gives the largest possible discount.

Any smaller candy would waste potential savings.

This greedy strategy always maximizes the value of free candies while preserving the validity condition.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries all possible valid groupings
Optimal	O(n log n)	O(1) or O(n) depending on sorting	Sort descending, skip every third candy

Algorithm Walkthrough

1. Sort the cost array in descending order.

We want the most expensive candies first because the free candy should be as expensive as possible. Sorting allows us to greedily form optimal groups. 2. Initialize a variable total_cost = 0.

This variable will accumulate the total amount we actually pay. 3. Iterate through the sorted array using an index.

The candies are processed in groups of three:

• First candy, paid
• Second candy, paid
• Third candy, free

4. Add the first and second candies of each group to total_cost.

Since these are the purchased candies, they contribute to the total payment. 5. Skip the third candy in each group.

The third candy becomes the free candy under the discount rule. 6. Continue until all candies are processed.

If fewer than three candies remain at the end, they must all be purchased.

Why it works

After sorting in descending order, every third candy is less than or equal to the previous two candies. Therefore, it always satisfies the discount condition.

Choosing the third-largest candy as free in each group maximizes the amount discounted. Any alternative arrangement would either:

• produce a smaller free candy, reducing savings, or
• violate the discount rule.

Thus, the greedy strategy is optimal.

Python Solution

from typing import List

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

        total_cost = 0

        for i in range(len(cost)):
            # Every third candy is free
            if i % 3 != 2:
                total_cost += cost[i]

        return total_cost

The implementation begins by sorting the candies in descending order. This guarantees that every group of three candies is ordered from largest to smallest.

The loop processes each candy by index. The candies at indices:

• 0, 1 are paid
• 2 is free
• 3, 4 are paid
• 5 is free

This pattern repeats every three elements.

The condition:

if i % 3 != 2:

means:

• add the candy cost unless it is the third candy in a group.

The final result is the minimum amount required to purchase all candies.

Go Solution

package main

import "sort"

func minimumCost(cost []int) int {
	sort.Slice(cost, func(i, j int) bool {
		return cost[i] > cost[j]
	})

	totalCost := 0

	for i := 0; i < len(cost); i++ {
		// Every third candy is free
		if i%3 != 2 {
			totalCost += cost[i]
		}
	}

	return totalCost
}

The Go solution follows exactly the same greedy strategy as the Python implementation.

The main difference is the sorting syntax. Go uses sort.Slice with a custom comparator to sort the slice in descending order.

Go slices behave similarly to dynamic arrays, so no special handling is required for empty or small inputs. Integer overflow is also not a concern because the maximum possible sum is small:

100 candies * 100 cost = 10,000

which easily fits inside Go's int type.

Worked Examples

Example 1

Input: [1,2,3]

Step 1: Sort Descending

[3,2,1]

Step 2: Process Groups

Index	Candy	Action	Total
0	3	Pay	3
1	2	Pay	5
2	1	Free	5

Final answer:

5

Example 2

Input: [6,5,7,9,2,2]

Step 1: Sort Descending

[9,7,6,5,2,2]

Step 2: Process Groups

Index	Candy	Action	Total
0	9	Pay	9
1	7	Pay	16
2	6	Free	16
3	5	Pay	21
4	2	Pay	23
5	2	Free	23

Final answer:

23

Example 3

Input: [5,5]

Step 1: Sort Descending

[5,5]

Step 2: Process Groups

Index	Candy	Action	Total
0	5	Pay	5
1	5	Pay	10

No third candy exists, so no discount applies.

Final answer:

10

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) or O(n)	Depends on sorting implementation

The loop itself is linear, O(n), because each candy is processed exactly once.

The sorting step requires O(n log n) time, which dominates the total complexity.

The additional memory usage is minimal. Ignoring sorting internals, the algorithm only uses a few variables.

Test Cases

from typing import List

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

        total_cost = 0

        for i in range(len(cost)):
            if i % 3 != 2:
                total_cost += cost[i]

        return total_cost

solution = Solution()

assert solution.minimumCost([1, 2, 3]) == 5  # Basic example with one free candy
assert solution.minimumCost([6, 5, 7, 9, 2, 2]) == 23  # Multiple discount groups
assert solution.minimumCost([5, 5]) == 10  # Fewer than three candies

assert solution.minimumCost([10]) == 10  # Single candy
assert solution.minimumCost([1, 1, 1]) == 2  # All equal candies
assert solution.minimumCost([8, 7, 6]) == 15  # Exact group of three

assert solution.minimumCost([9, 8, 7, 6]) == 23  # One leftover candy
assert solution.minimumCost([9, 8, 7, 6, 5]) == 28  # Two leftover candies

assert solution.minimumCost([100] * 100) == 6700  # Large uniform input
assert solution.minimumCost([1, 2, 3, 4, 5, 6]) == 16  # Multiple full groups

assert solution.minimumCost([2, 2, 2, 2, 2, 2]) == 8  # Repeated values
assert solution.minimumCost([10, 1, 1]) == 11  # Cheapest candy becomes free

print("All tests passed!")

Test	Why
[1,2,3]	Smallest nontrivial discount case
[6,5,7,9,2,2]	Multiple discount groups
[5,5]	No discount possible
[10]	Single-element boundary case
[1,1,1]	Equal-value candies
[8,7,6]	Exact group of three
[9,8,7,6]	One leftover candy
[9,8,7,6,5]	Two leftover candies
[100] * 100	Maximum-size stress test
[1,2,3,4,5,6]	Multiple complete groups
[2,2,2,2,2,2]	Duplicate-heavy input
[10,1,1]	Verifies legal free candy selection

Edge Cases

One important edge case occurs when the array contains fewer than three candies. In this situation, no free candy can ever be obtained because the discount requires purchasing two candies first. A buggy implementation might incorrectly attempt to skip a candy anyway. The current solution handles this naturally because no index satisfies i % 3 == 2.

Another important edge case is when the number of candies is not divisible by three. For example, with four or five candies, the final one or two candies cannot form a complete discount group. The algorithm correctly charges for all remaining candies because only every third candy is skipped.

A third edge case involves duplicate candy prices. Some implementations incorrectly assume unique values or rely on strict inequalities. However, the discount rule allows the free candy to be equal to the cheaper purchased candy. Sorting and grouping work correctly even when many candies share the same price.

A final subtle case is when the cheapest candies appear mixed with expensive candies in the original order. Since the algorithm sorts the array first, it does not depend on the original arrangement. This guarantees that the largest eligible candies are always selected as free candies, maximizing savings.