This is a very common coding interview problem that teaches how to distribute items fairly.
In this blog, we will understand the problem from zero level and then solve it step-by-step using JavaScript.
🧾 Problem in Simple Words
We have many chocolate packets.
Each packet has some chocolates.
Example:
arr = [7, 3, 2, 4, 9, 12, 56]
This means:
- Packet 1 → 7 chocolates
- Packet 2 → 3 chocolates
- Packet 3 → 2 chocolates
- Packet 4 → 4 chocolates
- Packet 5 → 9 chocolates
- Packet 6 → 12 chocolates
- Packet 7 → 56 chocolates
We also have students:
m = number of students
Example:
m = 3
So we must give exactly 1 packet to each student.
🎯 Goal (Most Important Part)
We must choose m packets such that:
maximum chocolates − minimum chocolates
is as small as possible.
This is called minimized difference.
🤔 Why Difference?
Because we want fair distribution.
Bad distribution:
[2, 3, 56]
diff = 56 − 2 = 54 ❌ unfair
Good distribution:
[2, 3, 4]
diff = 4 − 2 = 2 ✅ fair
So we always prefer packets that are close in value.
🔑 Important Observation
If we sort the packets, similar values come together.
Example:
Original: [7, 3, 2, 4, 9, 12, 56]
Sorted: [2, 3, 4, 7, 9, 12, 56]
Now close chocolate counts are neighbors.
So the best m packets will always be next to each other in sorted array.
This is the key idea of the problem.
🧠 Approach Step-by-Step
Step 1 → Sort the array
Step 2 → Take m consecutive packets
Step 3 → Find difference
Step 4 → Move window
Step 5 → Keep minimum
This is called sliding window.
📦 Example Walkthrough 1
arr = [7, 3, 2, 4, 9, 12, 56]
m = 3
Sort:
[2, 3, 4, 7, 9, 12, 56]
Now take groups of 3:
[2,3,4] → diff = 4−2 = 2
[3,4,7] → diff = 7−3 = 4
[4,7,9] → diff = 9−4 = 5
[7,9,12] → diff = 12−7 = 5
[9,12,56] → diff = 56−9 = 47
Minimum = 2
So answer = 2
📦 Example Walkthrough 2
arr = [1, 4, 7, 8, 9]
m = 3
Sort:
[1, 4, 7, 8, 9]
Now take groups of 3:
[1,4,7] → diff = 7−1 = 6
[4,7,8] → diff = 8−4 = 4
[7,8,9] → diff = 9−4 = 2
Minimum = 2
So answer = 2
💻 JavaScript Code (Easy)
function findMinDiff(arr, m) {
// Step 1: sort chocolates
arr.sort((a, b) => a - b);
let minDiff = Number.MAX_SAFE_INTEGER;
// window pointers
let start = 0;
let end = m - 1;
// Step 2: slide window
while (end < arr.length) {
let diff = arr[end] - arr[start];
if (diff < minDiff) {
minDiff = diff;
}
start++;
end++;
}
return minDiff;
}
▶️ Test
console.log(findMinDiff([7, 3, 2, 4, 9, 12, 56], 3));
Output:
2
🔍 Code Explanation Line-by-Line
Sort array
arr.sort((a, b) => a - b);
Now chocolates are in increasing order.
Store minimum difference
let minDiff = Number.MAX_SAFE_INTEGER;
Start with very large number.
Create window of size m
let start = 0;
let end = m - 1;
Example:
m = 3
start = 0
end = 2
window = [2,3,4]
Slide window
while (end < arr.length)
Move window one step each time.
Calculate difference
let diff = arr[end] - arr[start];
Because:
max = arr[end]
min = arr[start]
Update minimum
if (diff < minDiff) {
minDiff = diff;
}
Keep best answer.
Move window
start++;
end++;
Next group.
⏱ Time Complexity
Sorting:
O(n log n)
Sliding window:
O(n)
Total:
O(n log n)
🧩 Why This Solution is Correct
After sorting:
- closest numbers stay together
- best packets must be neighbors
- checking neighbors = checking all optimal choices
So sliding window finds best answer.
🏁 Final Understanding
We want to distribute chocolates fairly.
Fair means:
max − min → smallest
Sorting + sliding window checks all fair groups.
Minimum difference is the answer.
✅ Final Answer
Chocolate Distribution problem is solved by:
- Sorting packets
- Checking all groups of m packets
- Choosing group with minimum difference
Top comments (0)