Chocolate Distribution Problem Easy 0 attempts
GeeksforGeeks ↗

Chocolate Distribution Problem

Easy ArrayTwo Pointers GeeksforGeeks

You have N packets of chocolates, given as array A[] where A[i] is the chocolate count in the i-th packet, and M students to hand packets to. Choose M of the packets — one per student — so that the gap between the largest and smallest counts handed out is as small as possible, and return that minimum gap.

Input Format
Implement findMinDiff(arr, m). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
arr = [3,4,1,9,56,7,9,12]
m = 5
Output
6

Example 2

Input
arr = [1,10,20]
m = 1
Output
0
Constraints
  • 1 <= N <= 10^5
  • 1 <= A[i] <= 10^9
  • 1 <= M <= N
Test Cases (2)
Case 1
Args: [[3,4,1,9,56,7,9,12],5] Expected: 6
Case 2
Args: [[1,10,20],1] Expected: 0
Topics
ArrayTwo Pointers

Sort the array. Then slide a window of size m across the sorted array and find the window where the difference between the last and first element is minimized.

javascript
function findMinDiff(arr, m) {
  if (m === 0 || arr.length === 0) return 0;
  arr.sort((a, b) => a - b);

  let minDiff = Infinity;
  for (let i = 0; i + m - 1 < arr.length; i++) {
    const diff = arr[i + m - 1] - arr[i];
    minDiff = Math.min(minDiff, diff);
  }

  return minDiff;
}

Time: O(n log n) for sorting Space: O(1) (ignoring sort space)

Saved in this browser only. Private to you.

JavaScript