Chocolate Distribution Problem

Easy

Problem

arr[i] is the number of chocolates in packet i. Give one packet to each of m students so that the difference between the largest and smallest packet handed out is as small as possible. Return that minimum difference.

Example 1

Input:  arr = [7, 3, 2, 4, 9, 12, 56], m = 3
Output: 2

Choose packets 2, 3 and 4: 4 − 2 = 2.

Also asked as: Chocolate Distribution problem

Test cases

Case 1

Input:    [7,3,2,4,9,12,56], 3
Expected: 2

Case 2

Input:    [3,4,1,9,56,7,9,12], 5
Expected: 6

Case 3

Input:    [1,2,3], 3
Expected: 2

Case 4

Input:    [5], 1
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Sort + sliding window of size m

Time O(n log n)Space O(1)

After sorting, the fairest set of m packets is a contiguous window; minimise (window max − window min).

function minDiff(a, m) {
a.sort((x, y) => x - y);
let best = Infinity;
for (let i = 0; i + m - 1 < a.length; i++) {
best = Math.min(best, a[i + m - 1] - a[i]);
}
return best;
}