Chocolate Distribution problem

The problem, simply

You have n packets of chocolate. arr[i] is how many chocolates are in packet i. There are m kids, and each kid gets exactly one packet.

Pick m packets so that the difference between the fullest packet and the emptiest packet you hand out is as small as possible. Give back that smallest difference.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every way to choose m packets out of n. For each choice, find its biggest and smallest packet and keep the smallest gap.

1. Build groups one packet at a time: for each packet, either put it in the group or skip it.
2. When a group has m packets, compute max - min and keep the best.

class Solution {
    private int best;

    public int findMinDiff(int[] arr, int m) {
        if (m == 0 || m > arr.length) return -1;
        best = Integer.MAX_VALUE;
        choose(arr, m, 0, new ArrayList<>());
        return best;
    }

    private void choose(int[] arr, int m, int start, List<Integer> group) {
        if (group.size() == m) {                         // a full group of packets
            best = Math.min(best, Collections.max(group) - Collections.min(group));
            return;
        }
        for (int i = start; i < arr.length; i++) {
            group.add(arr[i]);                           // take packet i
            choose(arr, m, i + 1, group);
            group.remove(group.size() - 1);              // put it back
        }
    }
}

How long it takes: there are "n choose m" groups, written C(n, m), and each costs O(m) to check, so O(C(n, m) * m). For 50 packets and 25 kids that is more than a hundred trillion groups. Extra room: the group being built, O(m).

Way 2: the clever way

Sort the packets first. Now look at any good group. Its emptiest packet is some arr[i]. The best partners for it are the next m - 1 packets to its right, because any packet further right is bigger and can only make the gap worse. So the best group is always m packets that sit next to each other in sorted order.

1. Sort arr.
2. For every start i from 0 to n - m, the group is arr[i] to arr[i + m - 1], and its gap is arr[i + m - 1] - arr[i].
3. Keep the smallest gap.

class Solution {
    public int findMinDiff(int[] arr, int m) {
        int n = arr.length;
        if (m == 0 || m > n) return -1;
        Arrays.sort(arr);                                // line the bags up
        int best = Integer.MAX_VALUE;
        for (int i = 0; i + m - 1 < n; i++) {
            int gap = arr[i + m - 1] - arr[i];           // last in frame minus first
            best = Math.min(best, gap);
        }
        return best;
    }
}

How long it takes: sorting is O(n log n) and the slide is O(n), so O(n log n) in total. Extra room: a few numbers, O(1) (Java's sort for int[] uses a little stack space, about O(log n)).

Watch out for

• The window covers arr[i] to arr[i + m - 1], not arr[i + m]. Off by one here is the classic slip.
• Check m > n and m == 0 before sorting.
• Sorting changes the caller's array. Copy it first if the input must stay the same.

What interviewers ask next

• Return the actual packets, not only the gap. Remember the start i of the best frame and return arr[i..i+m-1].
• Can you avoid the sort? If the chocolate counts are small numbers, a counting sort makes it O(n + maxValue).
• Why is a block of neighbours always optimal? Fix the smallest packet in the best group. Swapping any other packet for a smaller unused one to its right never raises the maximum, so you can slide all of them next to the smallest.
• A cousin problem: make the heights of towers as even as possible by adding or removing k. That one also starts by sorting.

Remember this

Grown-up words: lining up the bags is sorting, the cardboard frame is a fixed size sliding window, and the unfairness is the range (max minus min) of the chosen subset.