Find minimum group of array with difference less than k

Question

I am working on code where I need to find the count of array group with difference between the elements of the array group should be less than k

Example The numbers of awards per movie are awards = [1, 5, 4, 6, 8, 9, 2], and the maximum allowed difference is k = 3.

One way to divide the movies into the minimum number of groups is:
The first group can contain [2, 1]. The maximum difference between awards of any two movies is 1 which does not exceed k.
The second group can contain [5, 4, 6]. The maximum difference between awards of any two movies is 2 which does not exceed k
The third group can contain [8, 9]. The maximum difference between awards of any two movies is 1 which does not exceed k. The movies can be divided into a minimum of 3 groups.

below is my code But it is not working. What I am doinng wrong. Please help me.

function minimumGroups(arr, k) {
    // Write your code here
arr.sort();
  let start = 0;
  if(arr.length == 0)
    return 0;
  // If arr has some value then at least can form 1 group
  let count = 1;
  for(let i = 0; i < arr.length; i++) {
    if(arr[i] - arr[start] > k) {
      count++;
      start = i;
    }
  }
  return count;
}

Some of hidden test cases are not passing for same scenario

Arr =[ 1, 13, 6, 8, 9, 3, 5 ] and K= 4 Expected output is 3 but I am getting 2

If this question is truly Java-related, please show the relevant Java code. Otherwise, please remove the [tag:java] tag. — Hovercraft Full Of Eels, Feb 25 '22 at 14:59
What do you mean "my code is not working". Tell or show us what it is doing, as opposed to what it should be doing. — RBarryYoung, Feb 25 '22 at 15:06
Please change `arr.sort()` to `arr.sort((a,b) => a-b);`. Just tried it for array `[ 1, 13, 6, 8, 9, 3, 5 ]` & it does output `3` as expected. Answer posted to quickly test as code-snippet. — jsN00b, Feb 25 '22 at 15:35
The title seems to be too general; you are not *really* asking about how to "find minimum group of array with difference less than k", since the answer to that question would presumably need to be a general algorithm with some explanation or guarantee that it actually finds the minimum. Instead, you are asking to find a bug in a particular code snippet that implements some algorithm which, if the bug were removed, may or may not find the minimum in all cases. You'd be better off [edit]ing the question to say that you're trying to sort an array and group by walking through the array... — jcalz, Feb 27 '22 at 19:10
... but that it's not behaving as you expect. The answer would then be that you are not actually sorting your array properly and that this question is essentially a duplicate of [this one](https://stackoverflow.com/q/1063007/2887218). Do you agree with this assessment or am I missing something? — jcalz, Feb 27 '22 at 19:11

score 1 · Accepted Answer · answered Feb 25 '22 at 15:37

This code snippet fixes the code by update the .sort().

function minimumGroups(arr, k) {
    // Write your code here
  arr.sort((a, b) => a-b);  // this line is updated.
  let start = 0;
  if(arr.length == 0) return 0;
  // If arr has some value then at least can form 1 group
  let count = 1;
  for(let i = 0; i < arr.length; i++) {
    if(arr[i] - arr[start] > k) {
      count++;
      start = i;
    }
  }
  return count;
};

console.log(minimumGroups([ 1, 13, 6, 8, 9, 3, 5 ], 4));

Find minimum group of array with difference less than k

1 Answers1