Arrays - Minimum Difference Between Highest and Lowest of K Scores

You are given a 0-indexed integer array nums, where nums[i] represents the score of the i^th 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.

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.

Constraints:

1 <= k <= nums.length <= 1000
0 <= nums[i] <= 10⁵

Solution 1 - Sort the array first, then find minimum diff window between i^th index and i+k^th index

In this approach, we are going to sort the input array nums, then with the sliding window of range K, check the difference between lowest element and highest element, and find the minimum value.

Implementation steps:

As a first step, sort the input array nums.
Next, create three variables left to point to starting position of sliding window, right to point to ending position of sliding window, and min variable to track the minimum value. We will initialize left = 0, right = k-1, because that is the starting sliding window range, and initialize min = Integer.MAX_VALUE since we are tracking minimum.
Because the nums array is sorted, value at left index will have the lowest value, and the value at right index will have the highest value, take the difference between these two values and and if it is less than min, update min with new value.
Repeat above step, until right index reaches the end of array, and finally return the min value.

import java.util.Arrays; public class MinimumDiffBetweenHighestAndLowestOfKScores { static int minimumDifference(int[] nums, int k) { Arrays.sort(nums); int left =0; int right = k-1; // kth index int min = Integer.MAX_VALUE; while(right<nums.length) { // because right index will reach end of array first int window = nums[right] - nums[left]; if(window < min) { min = window; } left++; right++; } return min; } public static void main(String[] args) { System.out.println(minimumDifference(new int[] {90}, 1)); System.out.println(minimumDifference(new int[] {9,4,1,7}, 2)); } }

Complexity Analysis:

Time complexity: Above code runs in O(n log n) time where n is the length of nums array. Sorting of array take O(n log n) and looping through finding the minimum takes O(n).
Space complexity: O(1), assuming that Arrays.sort(nums) uses an in-place sorting algorithm like QuickSort.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: