30. Chocolate Distribution Problem

You must give m students exactly one chocolate packet each, taken from n available packets (each has a chocolate count). To keep it fair, minimize the difference between the maximum and minimum packet sizes among the m chosen packets. Print that minimum difference.

Input: The first line contains n and m, space-separated. The second line contains n space-separated integers representing packet sizes. Output: Print a single integer - the minimum possible difference between the largest and smallest packet among the m chosen packets.

1 <= m <= n <= 10^5

This is structurally the same 'fixed-size sliding window over sorted data' pattern seen in problems like 'Minimise the Maximum Difference Between Heights' - recognizing the pattern transfers directly.

Give each of m students exactly one chocolate packet (each with a different amount of chocolate), choosing which packets to give out so the gap between the luckiest and unluckiest student is as small as possible. Brute force: Try every possible COMBINATION of m packets chosen from the n available ones directly, and check each combination's spread - this is combinatorially enormous (choosing m out of n), completely impractical for realistic n. Optimised: Sorting first reveals that the optimal choice of m packets is ALWAYS contiguous in sorted order - any non-contiguous selection could always be improved by swapping in a closer-together packet instead, so a sliding window of exactly size m over the sorted array is guaranteed to find the true optimum, checked in linear time after the sort.

Try every possible combination of m packets chosen out of the n available (not necessarily contiguous in the original order), compute the difference between the maximum and minimum in each combination, and keep the smallest difference found. This checks every possible selection directly and is guaranteed correct, but the number of combinations to check grows combinatorially with n and m. Time: O(C(n,m) * m) Space: O(m)

Sort the packet counts in ascending order (which is safe because the optimal selection of m packets is always a contiguous block once sorted - any non-contiguous choice can be improved by swapping in a closer-valued packet). Then, for every contiguous window of m elements in the sorted array, scan through all m elements of that window to find its max and min, compute the difference, and keep the smallest. This exploits sorting to reduce the search space to only n-m+1 candidate windows, but still redundantly rescans each window's elements from scratch to find its extremes. Time: O(n*m) Space: O(1)

Sort the packet counts once in ascending order, then observe that in a sorted array, the minimum and maximum of any contiguous window of size m are simply its first and last elements. Slide a window of size m across the sorted array one position at a time, computing the difference arr[i+m-1] - arr[i] for each window in O(1), and track the smallest difference seen. This removes the need to rescan each window's contents entirely, since sortedness guarantees the extremes are always at the window's two ends. Time: O(n log n) Space: O(1)

1. Sort all the packet sizes first. 2. Since the array is sorted, the m packets that minimize the spread between max and min are ALWAYS some contiguous window of m consecutive values in the sorted order (never a scattered selection). 3. Slide a window of exactly size m across the sorted array, and for each window position, compute (last element - first element) - that's the spread for that choice. 4. Track the smallest such spread found across every possible window position.

Time: O(n log n), dominated by the initial sort - the sliding window scan afterward is a single linear pass. Space: O(1) extra space beyond the sort itself.

m = n (all packets must be taken, fixing the difference to max-min of the whole array); m = 1 (any single packet works, so the difference is always 0); and n = 10^5 (largest, confirming the sort-and-slide-window approach is O(n log n)).

Be ready to justify WHY the optimal m packets must be contiguous once sorted - a common interview follow-up, and the entire reason this problem reduces to a simple sliding window instead of a combinatorial search.