Chocolate Distribution Problem

Q: What is the time complexity of the chocolate distribution problem?

Sorting takes O(n log n) and sliding the window of m packets takes O(n) , so the total is O(n log n) . The extra space is O(n) for a sorted copy, or O(1) beyond the sort itself if you sort the input in place.

Q: Is the chocolate distribution problem a sliding window problem?

Yes, a fixed-size window over the sorted packets. Unlike a running-sum window, there is nothing to update as it moves: each window's difference is one subtraction of its first packet from its last.

Q: Can the chocolate distribution problem be solved without sorting?

Sizes here are at most 10^5 , so a counting sort orders them in O(n + 10^5) time and the same slide follows. With unbounded sizes, comparisons alone cannot beat O(n log n) : with m = 2 the answer is 0 exactly when two packets are equal, and detecting a duplicate takes that many comparisons in the worst case.

EasySorting Sliding window

+10

You have some packets of chocolate, and packets[i] is the number of chocolates in packet i. Each of m students gets exactly one packet, so m different packets go out. Pick them so that the difference between the largest and the smallest packet handed out is as small as possible.

Write a function named minDifference that returns that smallest possible difference.

Function

minDifference(packets: integer-array, m: integer) → integer

packetsinteger-array: the number of chocolates in each packet
minteger: the number of students, each getting one packet
Returnsinteger: the smallest possible difference between the largest and smallest packet handed out

Constraints

2 ≤ m ≤ packets.length ≤ 10⁴
1 ≤ packets[i] ≤ 10⁵
Two packets can hold the same number of chocolates.

Examples

Input: packets = [9, 3, 15, 7, 11, 4]m = 3
Output: 4
Explanation: Sorted, the packets are 3, 4, 7, 9, 11 and 15. Both 3, 4, 7 and 7, 9, 11 give a difference of 4, and no three packets are closer together.

Input: packets = [8, 1, 5]m = 3
Output: 7
Explanation: There are three students and three packets, so every packet goes out and the difference is 8 - 1 = 7.

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Trying every group of m packets is far too slow. A best pick is always m packets that sit next to each other once the packets are sorted. So sort once, and the answer is the smallest difference across any window of m neighbors, found in one pass.

Fix the smallest packet

Correct, but does not finish on the largest tests

Intuition

Fix the smallest packet you hand out, low. To keep the largest one small, take the m-1 smallest packets that hold at least low. The difference is then the m-th smallest packet of at least low, minus low. Try every packet as low, skip any with fewer than m packets at or above it, and keep the smallest difference.

Each of the n choices filters and sorts up to n packets: O(n² log n). With n = 10^4 different sizes, the sorts alone make about 6 × 10^8 comparisons.

Algorithm

Start best at a value no answer can exceed.
For each packet low, collect every packet holding at least low chocolates and sort them.
If there are at least m of them, the m-th smallest minus low is a candidate.
Keep the smallest candidate in best and return it.

def minDifference(packets, m):
    best = max(packets) - min(packets)  # no gap can be wider than this
    for low in packets:
        # The packets that could go out alongside low, smallest first (low is one of them).
        bigger = sorted(x for x in packets if x >= low)
        if len(bigger) >= m:
            best = min(best, bigger[m - 1] - low)
    return best

Sort and slide a window of m packets

Intuition

In sorted order, a window sizes[i..i+m-1] has its smallest packet first and its largest last, so its difference is sizes[i+m-1] - sizes[i].

A best pick can always be a window. If a pick skips a packet that lies between its smallest and its largest, swap that packet in for the largest. The smallest stays and the largest can only shrink, so the difference never grows. Repeat until no gap is left.

In the first example the windows of three give 4, 5, 4 and 6, so the answer is 4. The sort costs O(n log n) and the slide O(n).

Algorithm

Sort the packets in increasing order into sizes.
Set best to sizes[m-1] - sizes[0], the first window.
For each start i from 1 to n-m, compare sizes[i+m-1] - sizes[i] with best and keep the smaller.
Return best.

def minDifference(packets, m):
    sizes = sorted(packets)
    best = sizes[m - 1] - sizes[0]
    # The window sizes[i..i+m-1] holds m packets; its first is the smallest, its last the largest.
    for i in range(1, len(sizes) - m + 1):
        best = min(best, sizes[i + m - 1] - sizes[i])
    return best

Pitfalls and edge cases

Ending the window at i+m instead of i+m-1, which measures m+1 packets.
Stopping one window early. Starts run from 0 through n-m inclusive. For [1, 10, 20, 21] with m = 2, a loop on i < n-m misses the only difference of 1.
Skipping the sort. In [9, 3, 15, 7, 11, 4] the first three packets differ by 12, while the answer is 4.
Measuring only the first window. The m smallest packets are one choice, but the best group can start anywhere.
Sorting numbers as text. In JavaScript, sort() without a comparator puts 100000 before 9.

Frequently asked questions3

What is the time complexity of the chocolate distribution problem?

Sorting takes O(n log n) and sliding the window of m packets takes O(n), so the total is O(n log n). The extra space is O(n) for a sorted copy, or O(1) beyond the sort itself if you sort the input in place.

Is the chocolate distribution problem a sliding window problem?

Yes, a fixed-size window over the sorted packets. Unlike a running-sum window, there is nothing to update as it moves: each window's difference is one subtraction of its first packet from its last.

Can the chocolate distribution problem be solved without sorting?

Sizes here are at most 10^5, so a counting sort orders them in O(n + 10^5) time and the same slide follows. With unbounded sizes, comparisons alone cannot beat O(n log n): with m = 2 the answer is 0 exactly when two packets are equal, and detecting a duplicate takes that many comparisons in the worst case.

def minDifference(packets, m):
    # Write code here

Test #1

Test #2

Test #3

Arguments

packets = [9, 3, 15, 7, 11, 4]
m = 3

Expected Output