Introduction

LeetCode 2144 – Minimum Cost of Buying Candies With Discount is a classic greedy + sorting problem.

The question looks simple initially, but the key challenge is understanding:

1. Which candies should be free?
2. How can we minimize the total payment?
3. Why sorting helps?

This is a good beginner-friendly greedy interview problem that teaches how to maximize discounts strategically.

Problem Link

🔗 Minimum Cost of Buying Candies With Discount

Problem Statement

A candy shop offers a discount:

For every two candies bought, you can get one additional candy for free.

Condition:

1. The free candy’s price must be less than or equal to the cheaper purchased candy.

You are given an array:

representing candy prices.

Return the minimum total amount needed to buy all candies.

Example 1

Input

Output

Explanation

Buy:

Get:

Total:

Example 2

Input

Output

Intuition

To maximize savings:

The most expensive candies should be grouped together.

Why?

Because every third candy becomes free.

So we want:

1. Expensive candies paid
2. Cheapest among the group free

Key Greedy Observation

If we sort candies in descending order:

Then:

1. Pay 9
2. Pay 7
3. Get 6 free

Then:

1. Pay 5
2. Pay 2
3. Get 2 free

This produces maximum discount.

Brute Force Approach

Idea

Try every grouping combination:

1. Select 2 candies
2. Choose possible free candy
3. Compute total minimum

Why Brute Force is Bad

The number of combinations becomes huge.

Time complexity becomes exponential.

Not suitable for interviews.

Optimized Greedy Approach

Steps

1. Sort candies in descending order
2. Traverse array
3. Skip every 3rd candy
4. Add remaining candies to answer

Java Solution

Cleaner Optimized Version

You can simplify the logic further:

Why This Works

After descending sorting:

Every 3rd candy becomes free.

This guarantees:

Dry Run

Input

Step 1: Sort Descending

Step 2: Traverse

Group 1

Total:

Group 2

Total:

Final Answer

Time Complexity Analysis

Sorting

Traversal

Total Complexity

Space Complexity

Because of extra reversed array.

Optimized Version

Ignoring sorting space.

Interview Explanation

In interviews explain:

To maximize savings, we should make the free candies as expensive as possible. Sorting in descending order ensures every third candy is the maximum eligible free candy.

This demonstrates:

1. Greedy thinking
2. Sorting optimization
3. Mathematical observation skills

Common Mistakes

1. Sorting Ascending

Ascending order gives smaller discounts.

Descending order is necessary.

2. Forgetting Every 3rd Candy is Free

Correct pattern:

Pay, Pay, Free

3. Using Extra Arrays Unnecessarily

You can directly traverse sorted array backward.

4. Incorrect Grouping

Always group expensive candies together.

FAQs

Q1. Why descending sorting?

To maximize free candy value.

Q2. Why skip every third candy?

Because the offer gives:

1 free candy after buying 2

Q3. Can this be solved without sorting?

Not optimally.

Sorting guarantees best grouping.

Q4. Is this a greedy problem?

Yes.

This is a classic greedy sorting optimization problem.

Conclusion

LeetCode 2144 is an excellent beginner greedy problem.

Main learning points:

1. Sorting strategy
2. Greedy grouping
3. Maximizing discounts
4. Efficient array traversal

The core insight is:

Sort candies from largest to smallest and make every third candy free.

Once this pattern becomes intuitive, many greedy interview problems become easier to solve.