Chocolate Distribution Problem

The problem, simply

You get n packets of chocolate. Packet i holds arr[i] pieces. There are m kids, and m is at most n. Every kid gets exactly one packet.

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

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every group of m packets. For each group, find its biggest and smallest packet. Keep the smallest gap.

1. Pick packets one by one, choosing "take" or "skip" for each, until m are taken.
2. For a full group, compute max - min.
3. Keep the smallest result.

class Solution {
    private int best;

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

    private void choose(int[] arr, int i, int m, List<Integer> group) {
        if (group.size() == m) {
            best = Math.min(best, Collections.max(group) - Collections.min(group));
            return;
        }
        if (arr.length - i < m - group.size()) return;   // not enough packets left
        group.add(arr[i]);                                // take packet i
        choose(arr, i + 1, m, group);
        group.remove(group.size() - 1);
        choose(arr, i + 1, m, group);                     // skip packet i
    }
}

How long it takes: there are C(n, m) groups, each checked in O(m), O(C(n, m) * m). Extra room: the current group, O(m).

Way 2: the clever way

Sort the packets. If you skip a packet in the middle of your group, you could swap it in for the biggest or the smallest one and the gap would not grow. So the best group is always m packets in a row in the sorted line.

1. Sort arr.
2. Slide a window of m packets: arr[i] to arr[i + m - 1].
3. The gap of each window is arr[i + m - 1] - arr[i]. Keep the smallest.

class Solution {
    public int findMinDiff(int[] arr, int m) {
        int n = arr.length;
        if (m == 0 || n == 0) return 0;
        Arrays.sort(arr);                        // close sizes now sit side by side

        int best = Integer.MAX_VALUE;
        for (int i = 0; i + m - 1 < n; i++) {
            int gap = arr[i + m - 1] - arr[i];   // biggest minus smallest in this window
            best = Math.min(best, gap);
        }
        return best;
    }
}

How long it takes: the sort is O(n log n) and the slide is O(n), so O(n log n). Extra room: O(1) besides what the sort uses.

Watch out for

• Off by one in the loop end. The last window starts at n - m, so the loop runs while i + m - 1 < n.
• m bigger than n has no answer. Decide what to return (many judges say it never happens).
• m = 0 or an empty array: return 0.
• Sorting changes the caller's array. Copy it first if that matters.

What interviewers ask next

• Why must the best group be in a row after sorting? If a packet between the smallest and biggest chosen ones is left out, swapping it for an end packet never makes the gap bigger. Repeat until the group has no holes.
• What if the packets cannot be reordered and the kids must take m packets that sit next to each other on the shelf? Slide the window over the original order and keep the window's smallest and biggest with two double ended queues. That is O(n).
• Minimum difference between the highest and lowest of k scores (LeetCode 1984) is exactly this problem.
• Can you avoid the full sort? If values are small, counting sort makes it O(n + maxValue).

Remember this

Grown-up words: the frame over the bags is a fixed size sliding window, lining up the bags is sorting, and "no holes in the best group" is the reason the window is enough.