Chocolate Distribution Problem — Problem & Solution
Chocolate Distribution Problem solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Chocolate Distribution Problem is an easy coding problem on arrays, sorting and sliding window, asked in TCS, Wipro and Accenture interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting, Sliding Window
- Asked at: TCS, Wipro, Accenture
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
arr[i] is the number of chocolates in the i-th packet. You must hand out exactly m packets to m students — one packet each.
Choose the packets so that the difference between the largest and the smallest packet given out is as small as possible, and return that difference.
Return 0 if m is 0, and -1 if there are fewer than m packets.
Example 1
Input: arr = [3,4,1,9,56,7,9,12], m = 5
Output: 6
Explanation: Choosing 3,4,7,9,9 spans 9 - 3 = 6.
Example 2
Input: arr = [7,3,2,4,9,12,56], m = 3
Output: 2
Explanation: Choosing 2,3,4 spans 4 - 2 = 2.
Example 3
Input: arr = [1,2], m = 5
Output: -1
Constraints
1 <= arr.length <= 1000000 <= m <= 1000001 <= arr[i] <= 1000000000
Hints for Chocolate Distribution Problem
Hint 1
The chosen packets do not have to be adjacent in the input — but after sorting, the best group always is.
Hint 2
Sort ascending, then look at every window of exactly
mconsecutive packets.Hint 3
The span of a sorted window is just
last - first.
How to solve Chocolate Distribution Problem
In a sorted array, the tightest set of m values is always a contiguous window: pulling in a value from outside a window can only widen the min-to-max span.
Approach
- Handle the guards:
m == 0answers0, andm > nanswers-1. - Sort a copy of
arrascending. - Slide a window of length
macross it, takings[i + m - 1] - s[i]at each position. - Return the smallest span seen.
Why it works
Suppose an optimal choice skipped some sorted value lying between its own minimum and maximum. Swapping the skipped value in for an endpoint keeps the count at m and cannot increase the span, so a contiguous window is always at least as good.
Complexity
- Time —
O(n log n) - Space —
O(n) for the sorted copy
Pitfalls
- Forgetting the
m > nguard indexes past the end of the array. - Windows must have exactly
melements — the loop bound isi + m - 1 < n. - With values up to 1e9 the difference still fits in 32 bits, but only because both endpoints are positive.
Reference solution
Python
from typing import List
def findMinDiff(arr: List[int], m: int) -> int:
if m == 0 or len(arr) == 0:
return 0
if m > len(arr):
return -1
s = sorted(arr)
best = s[m - 1] - s[0]
for i in range(len(s) - m + 1):
d = s[i + m - 1] - s[i]
if d < best:
best = d
return bestJava
public static int findMinDiff(int[] arr, int m) {
if (m == 0 || arr.length == 0) return 0;
if (m > arr.length) return -1;
int[] s = arr.clone();
Arrays.sort(s);
int best = s[m - 1] - s[0];
for (int i = 0; i + m - 1 < s.length; i++) {
int d = s[i + m - 1] - s[i];
if (d < best) best = d;
}
return best;
}C++
int findMinDiff(vector<int>& arr, int m) {
if (m == 0 || arr.empty()) return 0;
if (m > (int) arr.size()) return -1;
vector<int> s = arr;
sort(s.begin(), s.end());
int best = s[m - 1] - s[0];
for (int i = 0; i + m - 1 < (int) s.size(); i++) {
int d = s[i + m - 1] - s[i];
if (d < best) best = d;
}
return best;
}JavaScript
var findMinDiff = function(arr, m) {
if (m === 0 || arr.length === 0) return 0;
if (m > arr.length) return -1;
const s = arr.slice().sort(function(a, b) { return a - b; });
let best = s[m - 1] - s[0];
for (let i = 0; i + m - 1 < s.length; i++) {
const d = s[i + m - 1] - s[i];
if (d < best) best = d;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms