Chocolate Distribution Problem

Chocolate Distribution Problem

Given an array arr[] of positive integers, where each value represents the number of chocolates in a packet. Each packet can have a variable number of chocolates. There are m students, the task is to distribute chocolate packets among m students such that -
      i. Each student gets exactly one packet.
     ii. The difference between maximum number of chocolates given to a student and minimum number of chocolates given to a student is minimum and return that minimum possible difference.

Examples:

Input: arr = [3, 4, 1, 9, 56, 7, 9, 12], m = 5
Output: 6
Explanation: The minimum difference between maximum chocolates and minimum chocolates is 9 - 3 = 6 by choosing following m packets :[3, 4, 9, 7, 9].

Input: arr = [7, 3, 2, 4, 9, 12, 56], m = 3
Output: 2
Explanation: The minimum difference between maximum chocolates and minimum chocolates is 4 - 2 = 2 by choosing following m packets :[3, 2, 4].

Input: arr = [3, 4, 1, 9, 56], m = 5
Output: 55
Explanation: With 5 packets for 5 students, each student will receive one packet, so the difference is 56 - 1 = 55.

Constraints:
1 ≤ m <= arr.size ≤ 105
1 ≤ arr[i] ≤ 109

---

Approach

To solve the problem efficiently, we can use the sorting technique followed by a sliding window approach:

1. Sort the array: Sorting groups similar values together, allowing us to easily find the minimum and maximum values within any consecutive group of m elements.

2. Sliding Window of size m: Check the difference between the maximum and minimum values in each window of size m to find the minimum difference.

---

Java Code:

import java.util.Arrays;
public class ChocolateDistribution {
    public static int findMinDiff(int[] arr, int m) {
        if (arr.length < m) return -1; // Not enough packets
        Arrays.sort(arr); // Step 1: Sort the array
        int minDiff = Integer.MAX_VALUE;
        // Step 2: Find the min difference in any window of size m
        for (int i = 0; i + m - 1 < arr.length; i++) {
            int diff = arr[i + m - 1] - arr[i];
            minDiff = Math.min(minDiff, diff);
        }
        return minDiff;
    }
    public static void main(String[] args) {
        int[] arr1 = {3, 4, 1, 9, 56, 7, 9, 12};
        int m1 = 5;
        System.out.println(findMinDiff(arr1, m1)); // Output: 6
        int[] arr2 = {7, 3, 2, 4, 9, 12, 56};
        int m2 = 3;
        System.out.println(findMinDiff(arr2, m2)); // Output: 2
    }
}

---

Time Complexity:

• Sorting: O(n log n)

• Sliding Window: O(n)

Total: O(n log n)

---

Other Approaches:

1. Brute Force Approach
   Idea: Check all combinations of m packets and find the minimum difference.
   Time Complexity: O(n^m) (very inefficient)
   Not recommended for large inputs.

2. Sort + Sliding Window Approach (Optimal)
   Time Complexity: O(n log n)
   Space Complexity: O(1)
   Best for large inputs.

   
   Arrays.sort(arr);
   int minDiff = Integer.MAX_VALUE;
   for (int i = 0; i + m - 1 < arr.length; i++) {
       int diff = arr[i + m - 1] - arr[i];
       minDiff = Math.min(minDiff, diff);
   }
   
   

3. Min Heap Approach (Suboptimal)
   Time Complexity: O(n log n) for sorting + heap operations
   Space Complexity: O(m)
   Not commonly used unless the array is too large to sort in memory.

4. Greedy Approach Using Sort
   This approach is essentially the same as the optimal one but viewed through a greedy lens: choose the group of m chocolates that minimizes the max - min.

5. Two-Pointer Technique (After Sorting)
   Time Complexity: O(n log n)
   Similar to the sliding window, but explicitly uses two pointers start and end to iterate over windows of size m.

   
   int i = 0, j = m - 1;
   int minDiff = Integer.MAX_VALUE;
   while (j < arr.length) {
       minDiff = Math.min(minDiff, arr[j] - arr[i]);
       i++;
       j++;
   }
   

6. Bucket Sort Based (When arr[i] range is small)
   Time Complexity: O(n + range)
   Space Complexity: O(range)
   Useful if arr[i] values are small (e.g., up to 10^4).

---

Summary Table:

Approach	Time Complexity	Space Complexity	When to Use
Brute Force	O(n^m)	High	Never (slow)
Sort + Sliding Window	O(n log n)	O(1)	Best for large inputs
Min Heap	O(n log n)	O(m)	Rare case
Two Pointer After Sorting	O(n log n)	O(1)	Good
Bucket Sort	O(n + range)	O(range)	If arr[i] is small

---

Here is the corrected version of the code you provided. The issue is that you are using arr.length, but since arr is an ArrayList, you should use arr.size() instead. Also, you need to return the minDiff at the end of the method.

✅ Corrected Code:

import java.util.ArrayList;
class Solution {
    public int findMinDiff(ArrayList<Integer> arr, int m) {
        // If the number of packets is less than the number of students, return -1
        if (arr.size() < m) {
            return -1;
        }
        // Sort the array to bring similar values together
        arr.sort(null);
        int minDiff = Integer.MAX_VALUE;
        // Use a sliding window to find the minimum difference
        for (int i = 0; i + m - 1 < arr.size(); i++) {
            int diff = arr.get(i + m - 1) - arr.get(i);
            minDiff = Math.min(minDiff, diff);
        }
        return minDiff;
    }
}
 
 

🏃‍♂️ Explanation:

• First, the list is sorted to bring similar values together.

• Then, a sliding window approach is used to find the minimum difference between the largest and smallest chocolates in any window of size m.