Minimum and Maximum Cost to Buy All Candies

Minimum and Maximum Cost to Buy All Candies is a classic greedy warm-up. There is a "buy one, get k free" deal at the candy shop, and the same simple sort answers two opposite questions: what is the cheapest way to walk out with everything, and what is the most expensive?

The slow way first

You might imagine trying every grouping of candies into paid-plus-free bundles to see which assignment is cheapest, then which is dearest. The number of ways to partition the list explodes — that brute-force search is exponential and hopeless for a real list.

The question to ask: which candies should I actually pay for? The free candies are pure profit, so I want my paid set to be as cheap as possible (for the minimum) or as dear as possible (for the maximum). That is a greedy choice, and a single sort makes it obvious.

The idea: sort, then pay from one end

Sort the prices ascending. Each "purchase" claims 1 paid candy + k free candies, so the candies naturally fall into blocks of size k + 1.

• Minimum: sweep from the expensive end. In each block you are forced to pay for one candy — make it the dearest of the block and let the k cheaper ones below it ride free.
• Maximum: sweep from the cheap end. Pay for the cheapest of each block and let the k most expensive ride free.

The key insight: the free candies cost nothing, so to minimize you want the cheapest candies to be the free ones, and to maximize you want the dearest candies to be free. Sorting lines them up so a fixed stride of k + 1 picks exactly the right ones to pay for.

Walk through it

Step through the animation. After sorting [1, 2, 3, 4, 5, 6], the minimum pass pays for 6 then 3 (stepping left by k + 1 = 3 each time) and the cheap four go free → 9. The maximum pass pays for 1 then 2 (stepping right by 3) and the dear four go free → 3. The two running cost labels track each strategy.

Pseudocode

sort cost ascending
n = length of cost
 
# minimum: pay for the dearest in each block
min_total = 0
i = n - 1
while i >= 0:
    min_total += cost[i]      # pay for this candy
    i -= (k + 1)              # skip the k free ones below it
 
# maximum: pay for the cheapest in each block
max_total = 0
j = 0
while j < n:
    max_total += cost[j]      # pay for this candy
    j += (k + 1)             # skip the k free ones above it
 
return (min_total, max_total)

The Python solution

def min_max_cost(cost, k):
    cost.sort()
    n = len(cost)
    # minimum: buy the dearest, k cheapest go free
    min_total = 0
    i = n - 1
    while i >= 0:
        min_total += cost[i]
        i -= 1 + k
    # maximum: buy the cheapest, k dearest go free
    max_total = 0
    j = 0
    while j < n:
        max_total += cost[j]
        j += 1 + k
    return min_total, max_total

• cost.sort() lines the candies up cheapest-first — the one move that makes both greedy choices trivial.
• For the minimum, i starts at the last (most expensive) index and steps back by 1 + k, so we pay for the top of each block and skip the k cheaper candies below it.
• For the maximum, j starts at the cheapest index and steps forward by 1 + k, paying for the bottom of each block and skipping the k dearer candies above it.
• Each while loop just sums the candies we land on; the stride 1 + k is what guarantees the free candies are the right ones.
• We return both totals as a tuple.

Complexity

Sorting dominates at O(n log n); the two passes are linear and use only a couple of counters, so extra space is O(1) (ignoring the sort itself). The whole trick is recognizing that a greedy choice on a sorted list is optimal.

When this pattern shows up

Practice