Chocolate Distribution Problem

Intuition

Sort packets. The minimum difference between max and min packets given to m students is found in the sliding window of size m after sorting.

Algorithm

1Sort the packet array.
2Sliding window of size m: for each window, compute A[i+m-1] - A[i].
3Return minimum such difference.

Example Walkthrough

Input: A=[7,3,2,4,9,12,56], m=3

1.Sorted: [2,3,4,7,9,12,56].
2.Windows of size 3: [2,3,4]â†’2, [3,4,7]â†’4, [4,7,9]â†’5, [7,9,12]â†’5, [9,12,56]â†’47.
3.Min=2.

Output: 2

Common Pitfalls

•Sort first â€” only then is the minimum range guaranteed to be a contiguous subarray.

Chocolate Distribution Problem.java

Java

// Approach: Sort the array. Slide a window of size m and find the window with minimum (max - min).
// Time: O(n log n) Space: O(1)
import java.util.*;

class Solution {
    public int findMinDiff(ArrayList<Integer> arr, int m) {
        int n = arr.size();
        if (m == 0 || n == 0 || m > n)
            return 0;

        Collections.sort(arr);

        int res = Integer.MAX_VALUE;

        for (int i = 0; i <= n - m; i++) {
            int diff = arr.get(i + m - 1) - arr.get(i);
            res = Math.min(res, diff);
        }

        return res;
    }
}

Was this solution helpful?