Find the minimum and maximum amount to buy all N candies

The problem, simply

A candy shop has n different candies with prices prices[i]. The shop has a deal: every time you pay for one candy, you may take up to K other candies for free. Any candies, any price.

You must end up with every candy. Give back two numbers: the least money you could spend, and the most money you could spend.

A story to remember it

Picture it

Examples

Way 1: the simple way

Act it out with a list of the candies still on the shelf, without sorting.

1. For the least: while the shelf is not empty, find the cheapest candy, pay for it and remove it. Then remove the most expensive candy K times, for free.
2. For the most: same, but pay for the most expensive and remove the cheapest K times.

class Solution {
    public long[] candyStore(int[] prices, int K) {
        return new long[]{ act(prices, K, true), act(prices, K, false) };
    }

    private long act(int[] prices, int K, boolean cheap) {
        List<Integer> shelf = new ArrayList<>();
        for (int p : prices) shelf.add(p);
        long paid = 0;
        while (!shelf.isEmpty()) {
            paid += shelf.remove(pick(shelf, cheap));          // pay for this one
            for (int k = 0; k < K && !shelf.isEmpty(); k++) {
                shelf.remove(pick(shelf, !cheap));             // take this one free
            }
        }
        return paid;
    }

    // index of the cheapest candy (cheap = true) or the most expensive one
    private int pick(List<Integer> shelf, boolean cheap) {
        int best = 0;
        for (int i = 1; i < shelf.size(); i++) {
            boolean better = cheap ? shelf.get(i) < shelf.get(best) : shelf.get(i) > shelf.get(best);
            if (better) best = i;
        }
        return best;
    }
}

How long it takes: every candy leaves the shelf once, and finding it scans the shelf, so O(n^2). Extra room: the shelf list, O(n).

Way 2: the clever way

Sort the prices once and use two fingers, one at each end.

1. Sort the prices from cheap to expensive.
2. Least: buy starts at the cheap end, free at the expensive end. Pay prices[buy], move buy one step right, move free K steps left. Stop when they cross.
3. Most: the mirror image. Pay from the expensive end and take free candies from the cheap end.

A neat check: either way you pay for exactly ceil(n / (K + 1)) candies. The least is the sum of that many cheapest prices, and the most is the sum of that many priciest ones.

class Solution {
    public long[] candyStore(int[] prices, int K) {
        int[] p = prices.clone();
        Arrays.sort(p);
        int n = p.length;

        long min = 0;
        for (int buy = 0, free = n - 1; buy <= free; buy++, free -= K) {
            min += p[buy];            // pay the cheapest left, K priciest go free
        }

        long max = 0;
        for (int buy = n - 1, free = 0; free <= buy; buy--, free += K) {
            max += p[buy];            // pay the priciest left, K cheapest go free
        }
        return new long[]{min, max};
    }
}

How long it takes: the sort is O(n log n), the two walks are O(n). Extra room: the sorted copy, O(n).

Watch out for

• When free passes buy in the middle of a jump, stop. The loop condition buy <= free handles it.
• Sums can pass int for big shops. Use long.
• Some versions add a rule that the free candy must cost no more than the paid one. That is a different problem; read the statement.
• K = 0 means no deal. Both answers are the full sum.

What interviewers ask next

• Answer many queries with different K? Sort once and build prefix sums. For each K, the number paid is c = ceil(n / (K + 1)), the least is the sum of the first c prices and the most is the sum of the last c. Each query is O(1).
• Why is greedy safe here? You must pay for at least ceil(n / (K + 1)) candies, and the greedy pays for exactly that many, the cheapest possible ones. Nothing can do better.
• The "buy two, get a third that costs no more than either of them free" variant (LeetCode 2144)? Sort from priciest to cheapest and skip every third candy.

Remember this

Grown-up words: the two fingers are two pointers, the deal sets how many items are paid for, and the prefix sum trick answers many K values fast.