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 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 1:

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.

Example 2:

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] <= 105
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 10
    integer, dimension(n) :: nums
    integer :: k
    integer :: i

    ! Examples
    nums = reshape([90, 9, 4, 1, 7, 6, 5, 4, 6, 7], shape(nums))
    k = 1
    write(*,*) 'Example 1:'
    call solve(nums, k)
    write(*,*) ''
    nums = reshape([9, 4, 1, 7], shape(nums))
    k = 2
    write(*,*) 'Example 2:'
    call solve(nums, k)
    write(*,*) ''

contains

    subroutine solve(nums, k)
        implicit none
        integer, dimension(:), intent(in) :: nums
        integer, intent(in) :: k
        integer :: min_diff

        if (size(nums) < k .or. k < 1) then
            write(*,*) 'Invalid input'
            return
        end if

        min_diff = huge(0)
        do i = 1, size(nums) - k + 1
            min_diff = min(min_diff, maxval(nums(i:i+k-1)) - minval(nums(i:i+k-1)))
        end do

        write(*,*) 'Minimum possible difference: ', min_diff

    end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module MinimumDifference
    implicit none
    private
    public :: minimumDifference
contains
    function minimumDifference(nums, k) result(minDiff)
        integer, intent(in) :: nums(:)
        integer, intent(in) :: k
        integer :: minDiff
        integer :: i, j, n, temp

        ! Sort the array in ascending order
        do i = 1, size(nums) - 1
            do j = i + 1, size(nums)
                if (nums(i) > nums(j)) then
                    temp = nums(i)
                    nums(i) = nums(j)
                    nums(j) = temp
                end if
            end do
        end do

        ! Initialize the minimum difference
        minDiff = huge(0)

        ! Loop through all possible combinations of k elements
        do i = 1, size(nums) - k + 1
            n = nums(i + k - 1) - nums(i)
            if (n < minDiff) then
                minDiff = n
            end if
        end do
    end function minimumDifference
end module MinimumDifference

! Test the module with the given examples
program testMinimumDifference
    use MinimumDifference
    implicit none
    integer, parameter :: nums1(1) = [90]
    integer, parameter :: nums2(4) = [9, 4, 1, 7]
    integer, parameter :: nums3(5) = [3, 4, 5, 1, 2]
    integer, parameter :: nums4(6) = [9, 4, 1, 7, 9, 4]
    integer, parameter :: k1 = 1
    integer, parameter :: k2 = 2
    integer, parameter :: k3 = 3
    integer, parameter :: k4 = 4
    integer :: minDiff

    ! Test case 1:
    minDiff = minimumDifference(nums1, k1)
    if (minDiff /= 0) then
        write (*,*) "Test case 1 failed. Expected minimum difference = 0. Got", minDiff
        stop 1
    end if

    ! Test case 2:
    minDiff = minimumDifference(nums2, k2)
    if (minDiff /= 2) then
        write (*,*) "Test case 2 failed. Expected minimum difference = 2. Got", minDiff
        stop 1
    end if

    ! Test case 3:
    minDiff = minimumDifference(nums3, k3)
    if (minDiff /= 2) then
        write (*,*) "Test case 3 failed. Expected minimum difference = 2. Got", minDiff
        stop 1
    end if

    ! Test case 4:
    minDiff = minimumDifference(nums4, k4)
    if (minDiff /= 2) then
        write (*,*) "Test case 4 failed. Expected minimum difference = 2. Got", minDiff
        stop 1
    end if

    write (*,*) "All test cases passed!"
end program testMinimumDifference
🌐 Data from online sources 
def max_distance(nums1, nums2):
    i, j, max_dist = 0, 0, 0
    while i < len(nums1) and j < len(nums2):
        if i <= j and nums1[i] <= nums2[j]:
            max_dist = max(max_dist, j - i)
            j += 1
        else:
            i += 1
    return max_dist
  1. Initialize variables i and j to 0 and maxDist to 0.
  2. Loop with a while condition until we reach the end of either of the arrays.
  3. Check the valid pair condition: i <= j and nums1[i] <= nums2[j].
  4. If the pair is valid, calculate the distance as j - i and update maxDist if this distance is greater than its current value.
  5. Increment j to check the next element in array nums2.
  6. If the pair condition is not valid, increment i to check the next element in array nums1.
  7. Repeat steps 3-4 until the end of either array is reached.
  8. Return the maxDist as the maximum distance of a valid pair.
🌐 Data from online sources 
int maxDistance(vector<int>& nums1, vector<int>& nums2) {
    int i = 0, j = 0, maxDist = 0;
    while (i < nums1.size() && j < nums2.size()) {
        if (i <= j && nums1[i] <= nums2[j]) {
            maxDist = max(maxDist, j - i);
            j++;
        } else {
            i++;
        }
    }
    return maxDist;
}
  1. Initialize variables i and j to 0 and maxDist to 0.
  2. Loop with a while condition until we reach the end of either of the arrays.
  3. Check the valid pair condition: i <= j and nums1[i] <= nums2[j].
  4. If the pair is valid, calculate the distance as j - i and update maxDist if this distance is greater than its current value.
  5. Increment j to check the next element in array nums2.
  6. If the pair condition is not valid, increment i to check the next element in array nums1.
  7. Repeat steps 3-4 until the end of either array is reached.
  8. Return the maxDist as the maximum distance of a valid pair.