We have a skills array where skills[i] denotes the skill of the ith student. We are trying to from groups such that the maximum skill difference between any 2 individuals within the same group is at most k. Find the minimum number of groups required to achieve this.
Example:
skills = [7,2,9,1,13,4]
k = 3
#min groups required = 3
groups = ([1,2,4] , [7,9], [13])
I can implement this very easily in O(n logn) by sorting it and then simply iterating and checking if we still meet the condition of at most k or else form a new group.
However, I am looking for a more efficient solution in O(n).
Thanks!