ArrayProblem 30 of 36
Chocolate Distribution problem
Problem Statement
Given an array of n integers where each value represents the number of chocolates in a packet, distribute these packets to m students such that the difference between the maximum and minimum chocolates given to students is minimized.
Constraints:
- Each student gets exactly one packet
- m ≤ n
Example:
- Input:
arr = [7, 3, 2, 4, 9, 12, 56],m = 3 - Output:
2 - Explanation: If we distribute packets with 3, 4, and 2 chocolates, the difference is 4 - 2 = 2.
Approach 1: Brute Force
Intuition
Try all possible combinations of m packets and find the one with minimum difference between max and min chocolates.
Algorithm
- Generate all combinations of m packets from n packets
- For each combination, find max and min
- Track the minimum difference
java
import java.util.*;
public class Solution {
private int minDiff;
public int minDiffBruteForce(int[] arr, int m) {
int n = arr.length;
if (m > n) return -1;
minDiff = Integer.MAX_VALUE;
List<Integer> current = new ArrayList<>();
solve(arr, m, 0, current);
return minDiff;
}
private void solve(int[] arr, int m, int start, List<Integer> current) {
if (current.size() == m) {
int maxVal = Collections.max(current);
int minVal = Collections.min(current);
minDiff = Math.min(minDiff, maxVal - minVal);
return;
}
for (int i = start; i < arr.length; i++) {
current.add(arr[i]);
solve(arr, m, i + 1, current);
current.remove(current.size() - 1);
}
}
}Complexity Analysis
- Time Complexity: O(C(n,m) × m) = O(n² × m) for moderate values - generating combinations and finding min/max
- Space Complexity: O(m) - For storing current combination
Approach 2: Optimal - Sorting with Sliding Window
Intuition
After sorting, the minimum difference will be between m consecutive elements. We just need to find the window of m consecutive elements with minimum difference.
Algorithm
- Sort the array
- Use a sliding window of size m
- For each window, calculate difference (arr[i+m-1] - arr[i])
- Track the minimum difference
java
import java.util.Arrays;
public class Solution {
public int findMinDiff(int[] arr, int m) {
int n = arr.length;
// Edge cases
if (m == 0 || n == 0 || m > n) {
return -1;
}
// Sort the array
Arrays.sort(arr);
// Find minimum difference in sliding window of size m
int minDiff = Integer.MAX_VALUE;
for (int i = 0; i + m - 1 < n; i++) {
int diff = arr[i + m - 1] - arr[i];
minDiff = Math.min(minDiff, diff);
}
return minDiff;
}
}Complexity Analysis
- Time Complexity: O(n log n) - Dominated by sorting
- Space Complexity: O(1) - Only constant extra space (excluding sorting space)
Approach 3: Detailed Implementation with Edge Cases
Intuition
Same as Approach 2, but with comprehensive edge case handling.
Algorithm
- Handle all edge cases (empty array, m > n, m = 1)
- Sort the array
- Slide window and track minimum difference
- Return the result
java
import java.util.*;
public class Solution {
public int findMinDiff(int[] arr, int m) {
int n = arr.length;
// Edge cases
if (n == 0 || m == 0) return 0;
if (m > n) return -1;
if (m == 1) return 0; // Only one student
if (n == 1) return 0; // Only one packet
// Sort the array
Arrays.sort(arr);
// Initialize with first window
int minDiff = arr[m - 1] - arr[0];
// Slide window and find minimum difference
for (int i = 1; i + m - 1 < n; i++) {
int diff = arr[i + m - 1] - arr[i];
if (diff < minDiff) {
minDiff = diff;
}
}
return minDiff;
}
// Variation: Return the actual distribution
public int[] findMinDiffDistribution(int[] arr, int m) {
int n = arr.length;
if (n == 0 || m == 0 || m > n) return new int[]{};
Arrays.sort(arr);
int minDiff = Integer.MAX_VALUE;
int startIdx = 0;
for (int i = 0; i + m - 1 < n; i++) {
int diff = arr[i + m - 1] - arr[i];
if (diff < minDiff) {
minDiff = diff;
startIdx = i;
}
}
return Arrays.copyOfRange(arr, startIdx, startIdx + m);
}
}Complexity Analysis
- Time Complexity: O(n log n) - Dominated by sorting
- Space Complexity: O(1) - Only constant extra space
Key Takeaways
- Sorting transforms the problem - After sorting, optimal solution is always consecutive elements
- Sliding window for fixed-size subsets - Perfect for finding optimal contiguous elements
- Greedy after sorting - Many optimization problems become greedy after sorting
- Difference in sorted array - Max - Min in sorted contiguous subarray is just last - first
- Similar problems - Minimize max difference in groups, partition problems