.png)
Chocolate Distribution Problem
Problem Statement
You are given an array arr representing packets of chocolates, where each element denotes the number of chocolates in a packet.
You are also given an integer m, representing the number of students.
Your task is to distribute exactly one packet to each student such that the difference between the maximum and minimum chocolates received is minimum.
Example 1
Input
arr = [7, 3, 2, 4, 9, 12, 56]
m = 3
Output
2
Explanation
Choose packets [2, 3, 4] → max − min = 4 − 2 = 2
Example 2
Input
arr = [3, 4, 1, 9, 56, 7, 9, 12]
m = 5
Output
6
Why This Problem Is Important
Very common array + sorting interview question
Tests greedy thinking
Introduces sliding window on sorted data
Frequently asked in product companies
Foundation for allocation and minimization problems
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(nCm · m) | O(m) |
| Approach 2 | Sorting + Sliding Window (Optimal) | O(n log n) | O(1) |
| Approach 3 | Heap Based | O(n log n) | O(n) |
Approach 1: Brute Force
Idea
Check all possible combinations of m packets and calculate
max(chocolates) − min(chocolates) for each combination.
Algorithm
Initialize minDiff = infinity
Generate all combinations of size m
For each combination:
- Find min and max
- Update minDiff
Time & Space Complexity
Time: O(nCm · m)
Space: O(m)
Python
from itertools import combinations
def chocolateDistribution(arr, m):
minDiff = float('inf')
for comb in combinations(arr, m):
minDiff = min(minDiff, max(comb) - min(comb))
return minDiff
arr = [7,3,2,4,9,12,56]
m = 3
print(chocolateDistribution(arr, m))
Output
2
C++
#include
#include
#include
using namespace std;
int result = INT_MAX;
void DFS(vector& arr, int m, int idx, vector& temp) {
if(temp.size() == m) {
int mn = *min_element(temp.begin(), temp.end());
int mx = *max_element(temp.begin(), temp.end());
result = min(result, mx - mn);
return;
}
if(idx == arr.size()) return;
temp.push_back(arr[idx]);
DFS(arr, m, idx + 1, temp);
temp.pop_back();
DFS(arr, m, idx + 1, temp);
}
int main() {
vector arr = {7,3,2,4,9,12,56};
int m = 3;
vector temp;
DFS(arr, m, 0, temp);
cout << result;
}
Output
2
Java
import java.util.*;
class Main {
static int result = Integer.MAX_VALUE;
static void DFS(int[] arr, int m, int idx, List temp) {
if(temp.size() == m) {
int min = Collections.min(temp);
int max = Collections.max(temp);
result = Math.min(result, max - min);
return;
}
if(idx == arr.length) return;
temp.add(arr[idx]);
DFS(arr, m, idx + 1, temp);
temp.remove(temp.size() - 1);
DFS(arr, m, idx + 1, temp);
}
public static void main(String[] args) {
int[] arr = {7,3,2,4,9,12,56};
int m = 3;
DFS(arr, m, 0, new ArrayList<>());
System.out.print(result);
}
}
Output
2
C# (Corrected Generic List)
using System;
using System.Collections.Generic;
class Program {
static int result = int.MaxValue;
static void DFS(int[] arr, int m, int idx, List temp) {
if (temp.Count == m) {
int min = int.MaxValue, max = int.MinValue;
foreach (int x in temp) {
min = Math.Min(min, x);
max = Math.Max(max, x);
}
result = Math.Min(result, max - min);
return;
}
if (idx == arr.Length) return;
temp.Add(arr[idx]);
DFS(arr, m, idx + 1, temp);
temp.RemoveAt(temp.Count - 1);
DFS(arr, m, idx + 1, temp);
}
static void Main() {
int[] arr = {7,3,2,4,9,12,56};
int m = 3;
DFS(arr, m, 0, new List());
Console.WriteLine(result);
}
}
Output
2
Approach 2: Sorting + Sliding Window (Optimal)
Idea
Sort the array.
Consider every contiguous subarray of size m.
Minimum difference will lie in one of these windows.
Algorithm
Sort the array
Initialize minDiff = infinity
For i from 0 to n - m:
- diff = arr[i + m - 1] − arr[i]
- update minDiff
Time & Space Complexity
Time: O(n log n)
Space: O(1)
C
#include
#include
int cmp(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int main() {
int arr[] = {7,3,2,4,9,12,56};
int n = 7, m = 3;
qsort(arr, n, sizeof(int), cmp);
int minDiff = 1e9;
for(int i = 0; i <= n - m; i++) {
int diff = arr[i + m - 1] - arr[i];
if(diff < minDiff)
minDiff = diff;
}
printf("%d", minDiff);
return 0;
}
Output
2
C++
#include
#include
#include
using namespace std;
int main() {
int arr[] = {7,3,2,4,9,12,56};
int n = 7, m = 3;
sort(arr, arr + n);
int minDiff = INT_MAX;
for(int i = 0; i <= n - m; i++)
minDiff = min(minDiff, arr[i + m - 1] - arr[i]);
cout << minDiff;
return 0;
}
Output
2
Java
import java.util.Arrays;
public class ChocolateDistribution {
public static void main(String[] args) {
int[] arr = {7,3,2,4,9,12,56};
int m = 3;
Arrays.sort(arr);
int minDiff = Integer.MAX_VALUE;
for(int i = 0; i <= arr.length - m; i++)
minDiff = Math.min(minDiff, arr[i + m - 1] - arr[i]);
System.out.print(minDiff);
}
}
Output
2
Python
def chocolateDistribution(arr, m):
arr.sort()
minDiff = float('inf')
for i in range(len(arr) - m + 1):
minDiff = min(minDiff, arr[i + m - 1] - arr[i])
return minDiff
arr = [7,3,2,4,9,12,56]
m = 3
print(chocolateDistribution(arr, m))
Output
2
JavaScript
let arr = [7,3,2,4,9,12,56];
let m = 3;
arr.sort((a,b) => a - b);
let minDiff = Infinity;
for (let i = 0; i <= arr.length - m; i++) {
minDiff = Math.min(minDiff, arr[i + m - 1] - arr[i]);
}
console.log(minDiff);
Output
2
C#
using System;
class Program {
static void Main() {
int[] arr = {7,3,2,4,9,12,56};
int m = 3;
Array.Sort(arr);
int minDiff = int.MaxValue;
for(int i = 0; i <= arr.Length - m; i++)
minDiff = Math.Min(minDiff, arr[i + m - 1] - arr[i]);
Console.WriteLine(minDiff);
}
}
Output
2
Approach 3: Heap (Priority Queue)
Idea
Insert all elements into a min-heap to get sorted order,
then apply sliding window logic.
Time & Space Complexity
Time: O(n log n)
Space: O(n)
Python (Min Heap)
import heapq
def chocolateDistribution(arr, m):
heapq.heapify(arr)
sortedArr = []
while arr:
sortedArr.append(heapq.heappop(arr))
minDiff = float('inf')
for i in range(len(sortedArr) - m + 1):
minDiff = min(minDiff, sortedArr[i + m - 1] - sortedArr[i])
return minDiff
arr = [7,3,2,4,9,12,56]
m = 3
print(chocolateDistribution(arr, m))
Output
2
C#
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr = {7,3,2,4,9,12,56};
int m = 3;
PriorityQueue pq = new PriorityQueue();
foreach(int x in arr)
pq.Enqueue(x, x);
List sorted = new List();
while(pq.Count > 0)
sorted.Add(pq.Dequeue());
int minDiff = int.MaxValue;
for(int i = 0; i <= sorted.Count - m; i++)
minDiff = Math.Min(minDiff, sorted[i + m - 1] - sorted[i]);
Console.WriteLine(minDiff);
}
}
Output
2
Summary
- Brute force is intuitive but impractical
- Sorting + sliding window is optimal and preferred
- Heap approach is an alternative when sorting is restricted
- This is a classic greedy + sorting interview problem
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
