Chocolate Distribution Problem

Easy
506.

Chocolate Distribution Problem

Chocolate Distribution Problem is an easy coding problem on arrays, sorting and sliding window, asked in TCS, Wipro and Accenture interviews.

arr[i] is the number of chocolates in the i-th packet. You must hand out exactly m packets to m students — one packet each.

Choose the packets so that the difference between the largest and the smallest packet given out is as small as possible, and return that difference.

Return 0 if m is 0, and -1 if there are fewer than m packets.

Example 1

Input
arr = [3,4,1,9,56,7,9,12], m = 5
Output
6
Explanation
Choosing 3,4,7,9,9 spans 9 - 3 = 6.

Example 2

Input
arr = [7,3,2,4,9,12,56], m = 3
Output
2
Explanation
Choosing 2,3,4 spans 4 - 2 = 2.

Example 3

Input
arr = [1,2], m = 5
Output
-1

Constraints

  • 1 <= arr.length <= 100000
  • 0 <= m <= 100000
  • 1 <= arr[i] <= 1000000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} m
 * @return {number}
 */
var findMinDiff = function(arr, m) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Chocolate Distribution Problem — Problem & Solution

Chocolate Distribution Problem solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Chocolate Distribution Problem is an easy coding problem on arrays, sorting and sliding window, asked in TCS, Wipro and Accenture interviews.

Problem statement

arr[i] is the number of chocolates in the i-th packet. You must hand out exactly m packets to m students — one packet each.

Choose the packets so that the difference between the largest and the smallest packet given out is as small as possible, and return that difference.

Return 0 if m is 0, and -1 if there are fewer than m packets.

Example 1

Input: arr = [3,4,1,9,56,7,9,12], m = 5
Output: 6
Explanation: Choosing 3,4,7,9,9 spans 9 - 3 = 6.

Example 2

Input: arr = [7,3,2,4,9,12,56], m = 3
Output: 2
Explanation: Choosing 2,3,4 spans 4 - 2 = 2.

Example 3

Input: arr = [1,2], m = 5
Output: -1

Constraints

  • 1 <= arr.length <= 100000
  • 0 <= m <= 100000
  • 1 <= arr[i] <= 1000000000

Hints for Chocolate Distribution Problem

  1. Hint 1

    The chosen packets do not have to be adjacent in the input — but after sorting, the best group always is.

  2. Hint 2

    Sort ascending, then look at every window of exactly m consecutive packets.

  3. Hint 3

    The span of a sorted window is just last - first.

How to solve Chocolate Distribution Problem

In a sorted array, the tightest set of m values is always a contiguous window: pulling in a value from outside a window can only widen the min-to-max span.

Approach

  1. Handle the guards: m == 0 answers 0, and m > n answers -1.
  2. Sort a copy of arr ascending.
  3. Slide a window of length m across it, taking s[i + m - 1] - s[i] at each position.
  4. Return the smallest span seen.

Why it works

Suppose an optimal choice skipped some sorted value lying between its own minimum and maximum. Swapping the skipped value in for an endpoint keeps the count at m and cannot increase the span, so a contiguous window is always at least as good.

Complexity

  • Time — O(n log n)
  • Space — O(n) for the sorted copy

Pitfalls

  • Forgetting the m > n guard indexes past the end of the array.
  • Windows must have exactly m elements — the loop bound is i + m - 1 < n.
  • With values up to 1e9 the difference still fits in 32 bits, but only because both endpoints are positive.

Reference solution

Python

from typing import List

def findMinDiff(arr: List[int], m: int) -> int:
    if m == 0 or len(arr) == 0:
        return 0
    if m > len(arr):
        return -1
    s = sorted(arr)
    best = s[m - 1] - s[0]
    for i in range(len(s) - m + 1):
        d = s[i + m - 1] - s[i]
        if d < best:
            best = d
    return best

Java

public static int findMinDiff(int[] arr, int m) {
    if (m == 0 || arr.length == 0) return 0;
    if (m > arr.length) return -1;
    int[] s = arr.clone();
    Arrays.sort(s);
    int best = s[m - 1] - s[0];
    for (int i = 0; i + m - 1 < s.length; i++) {
        int d = s[i + m - 1] - s[i];
        if (d < best) best = d;
    }
    return best;
}

C++

int findMinDiff(vector<int>& arr, int m) {
    if (m == 0 || arr.empty()) return 0;
    if (m > (int) arr.size()) return -1;
    vector<int> s = arr;
    sort(s.begin(), s.end());
    int best = s[m - 1] - s[0];
    for (int i = 0; i + m - 1 < (int) s.size(); i++) {
        int d = s[i + m - 1] - s[i];
        if (d < best) best = d;
    }
    return best;
}

JavaScript

var findMinDiff = function(arr, m) {
    if (m === 0 || arr.length === 0) return 0;
    if (m > arr.length) return -1;
    const s = arr.slice().sort(function(a, b) { return a - b; });
    let best = s[m - 1] - s[0];
    for (let i = 0; i + m - 1 < s.length; i++) {
        const d = s[i + m - 1] - s[i];
        if (d < best) best = d;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms