[LeetCode] Minimum Difference Between Highest and Lowest of K Scores

Problem: You are given a 0-indexed integer array nums, where nums[i] represents the score of the ith student. You are also given an integer k.

Pick the scores of any k students from the array so that the difference between the highest and the lowest of the k scores is minimized.

Return the minimum possible difference.

Example:

Input: nums = [90], k = 1
Output: 0
Explanation: There is one way to pick score(s) of one student:
- [90]. The difference between the highest and lowest score is 90 - 90 = 0.
The minimum possible difference is 0.

Input: nums = [9,4,1,7], k = 2
Output: 2
Explanation: There are six ways to pick score(s) of two students:
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 4 = 5.
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 1 = 8.
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 7 = 2.
- [9,4,1,7]. The difference between the highest and lowest score is 4 - 1 = 3.
- [9,4,1,7]. The difference between the highest and lowest score is 7 - 4 = 3.
- [9,4,1,7]. The difference between the highest and lowest score is 7 - 1 = 6.
The minimum possible difference is 2.

Approach: We have to find the maximum and minimum value of each k size subarray so we can sort the array. Now what we just need to do is to take the subarray in sequence like nums[0...k-1], nums[1...k], nums[2...k+1] etc. Now if you see its easy to find the max and min value of these subarray as 1st value will be the minimum value and last value is the maximum value.

Now we just need to take the difference of these value and get the minimum of these differences which will be our answer.

Implementation in C#:

    public int MinimumDifference(int[] nums, int k)

    {

        int length = nums?.Length ?? 0;

        if (k > length)

        {

            return 0;

        }

        Array.Sort(nums);

        int min = int.MaxValue;    

        for (int i = 0; i + k <= length; ++i)

        {

            if (min > nums[i + k - 1] - nums[i])

            {

                min = nums[i + k - 1] - nums[i];

            }

        }

        return min;    

    }

Complexity: O(nlogn)