DSA Tracker

Visualize

Chocolate Distribution Problem

Sort, then slide a fixed window of m packets

time O(n log n)space O(1)

Fairness here is one number: largest packet handed out minus smallest. Sorting turns the search into a much smaller one, because in sorted order the m packets closest in size are always next to each other — reaching past a packet to grab a further one can only stretch the gap. So slide a window of exactly m packets across the sorted list; the difference between its two ends is that group's spread, and the smallest spread seen wins.

Details

Animated on: packets = 21, 3, 8, 5, 13, 17, 19, 30 and m = 4 students — hand one packet to each student so the biggest packet given out minus the smallest is as small as possible.

Problem:Chocolate Distribution ProblemEasy

Sort, then slide a fixed window of m packets

step 1 / 8

21
[0]
3
[1]
8
[2]
5
[3]
13
[4]
17
[5]
19
[6]
30
[7]

8 packets 21, 3, 8, 5, 13, 17, 19, 30 to hand out to 4 students, one packet each. We want the group of 4 where the biggest and smallest packet are as close as possible.

Pseudocode
1FUNCTION minSpread(packets, m):
2  packets <- SORT(packets)
3  best <- INFINITY
4  FOR i <- 0 TO LENGTH(packets) - m
5    j <- i + m - 1
6    spread <- packets[j] - packets[i]
7    IF spread < best
8      best <- spread
9  RETURN best

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. 8 packets 21, 3, 8, 5, 13, 17, 19, 30 to hand out to 4 students, one packet each. We want the group of 4 where the biggest and smallest packet are as close as possible.
  2. Sorted: 3, 5, 8, 13, 17, 19, 21, 30. Now the 4 closest-sized packets must sit side by side — skipping a packet to reach a further one only pulls the biggest and smallest further apart, never closer.
  3. Window 3, 5, 8, 13: largest 13 minus smallest 3 = 10. No group has been measured yet, so 10 is the spread to beat.
  4. Window 5, 8, 13, 17: largest 17 minus smallest 5 = 12. 12 is wider than the best spread so far (10), so this group is discarded — one student would do noticeably better than another.
  5. Window 8, 13, 17, 19: largest 19 minus smallest 8 = 11. 11 is wider than the best spread so far (10), so this group is discarded — one student would do noticeably better than another.
  6. Window 13, 17, 19, 21: largest 21 minus smallest 13 = 8. 8 beats the best spread so far (10), so these 4 packets are the fairest split we have found.
  7. Window 17, 19, 21, 30: largest 30 minus smallest 17 = 13. 13 is wider than the best spread so far (8), so this group is discarded — one student would do noticeably better than another.
  8. Every window of 4 has been measured. Give out 13, 17, 19, 21 — the smallest possible gap between the luckiest and unluckiest student is 8.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Chocolate Distribution Problem in the editorAll Arrays problemsBack to roadmap