Chocolate Distribution Problem

Problem Statement

Given an array of n packets where each packet contains some chocolates, and m students, distribute the packets such that:

1. Each student gets exactly one packet
2. The difference between the maximum and minimum chocolates given to any student is minimized

Return the minimum difference.

Constraints:

• 1 ≤ m ≤ n ≤ 10^5
• 1 ≤ arr[i] ≤ 10^9

Example:

• Input: arr = [3, 4, 1, 9, 56, 7, 9, 12], m = 5
• Output: 6
• Explanation: Select packets [3, 4, 7, 9, 9]. Max = 9, Min = 3, Difference = 6.

Example 2:

• Input: arr = [7, 3, 2, 4, 9, 12, 56], m = 3
• Output: 2
• Explanation: Select packets [2, 3, 4]. Max = 4, Min = 2, Difference = 2.

Approach 1: Brute Force (All Combinations)

Intuition

Try all possible combinations of selecting m packets from n packets. For each combination, calculate max - min and track the minimum difference.

Algorithm

1. Generate all C(n, m) combinations of packets
2. For each combination, find max and min
3. Calculate difference and track minimum
4. Return minimum difference found

import java.util.*;

public class Solution {
    private int minDiff = Integer.MAX_VALUE;
    
    private void findCombinations(int[] arr, int start, int m, List<Integer> current) {
        if (current.size() == m) {
            int maxVal = Collections.max(current);
            int minVal = Collections.min(current);
            minDiff = Math.min(minDiff, maxVal - minVal);
            return;
        }
        
        if (start >= arr.length) return;
        if (arr.length - start < m - current.size()) return;
        
        // Include current element
        current.add(arr[start]);
        findCombinations(arr, start + 1, m, current);
        current.remove(current.size() - 1);
        
        // Exclude current element
        findCombinations(arr, start + 1, m, current);
    }
    
    public int chocolateDistribution(int[] arr, int m) {
        if (m > arr.length) return -1;
        
        minDiff = Integer.MAX_VALUE;
        findCombinations(arr, 0, m, new ArrayList<>());
        
        return minDiff;
    }
}

Complexity Analysis

• Time Complexity: O(n² × m) - C(n,m) combinations, each taking O(m) to find max/min
• Space Complexity: O(m) - For storing current combination

Approach 2: Sliding Window with Sorting (Optimal)

Intuition

To minimize the difference between max and min, we should select m consecutive packets from a sorted array. Sorting ensures that consecutive elements have the smallest possible range.

Key Insight: After sorting, any optimal selection must be a contiguous subarray. If we skip an element in between, we could replace either endpoint with that element and not increase the range.

Algorithm

1. Sort the array
2. Use sliding window of size m
3. For each window, calculate arr[i+m-1] - arr[i]
4. Track and return minimum difference

import java.util.*;

public class Solution {
    public int chocolateDistribution(int[] arr, int m) {
        int n = arr.length;
        
        if (m > n) return -1;
        if (m == 0) return 0;
        
        // Sort the array
        Arrays.sort(arr);
        
        int minDiff = Integer.MAX_VALUE;
        
        // Sliding window of size m
        for (int i = 0; i <= n - m; i++) {
            int diff = arr[i + m - 1] - arr[i];
            minDiff = Math.min(minDiff, diff);
        }
        
        return minDiff;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] arr = {3, 4, 1, 9, 56, 7, 9, 12};
        System.out.println(sol.chocolateDistribution(arr, 5));  // Output: 6
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n log n) - Dominated by sorting
• Space Complexity: O(1) - Only using constant extra space (or O(n) depending on sort)

Edge Cases

Key Takeaways

1. Sorting Insight: After sorting, optimal selection is always contiguous
2. Sliding Window: Fixed-size window slides over sorted array
3. Greedy Property: Selecting consecutive elements minimizes range
4. Time Efficiency: O(n log n) due to sorting
5. Edge Cases: Handle m > n, m = 0, m = 1 separately
6. Real Application: Fair distribution problems, load balancing
7. Similar Problems: Minimum difference between largest and smallest K elements