1984.minimum-difference-between-highest-and-lowest-of-k-scores.md

1984. Minimum Difference Between Highest and Lowest of K Scores

Brute Force

We just iterate all the subarrays of size k and find the minimum difference.

fun minimumDifference(nums: IntArray, k: Int): Int {
    nums.sort()
    var diff = Int.MAX_VALUE
    for (i in 0..nums.size - k) {
        var highest = Int.MIN_VALUE
        var lowest = Int.MAX_VALUE
        for (j in i until i + k) {
            highest = maxOf(highest, nums[j])
            lowest = minOf(lowest, nums[j])
        }
        diff = minOf(diff, highest - lowest)
    }
    return diff
}

Sliding Window

Since the array is sorted, we can use a sliding window to find the minimum difference.

X, X, X, X, X, X, ...
   |----k---|
   ^        ^
  min      max

// Iterate all elements
fun minimumDifference(nums: IntArray, k: Int): Int {
    nums.sort()
    var diff = Int.MAX_VALUE
    for (i in 0 until nums.size) {
        if (i - k + 1 >= 0) diff = minOf(diff, nums[i] - nums[i - k + 1])
    }
    return diff
}

// Iterate the maximume element from `k - 1` to the end
fun minimumDifference(nums: IntArray, k: Int): Int {
    nums.sort()
    var diff = Int.MAX_VALUE
    for (i in k - 1 until nums.size) {
        diff = minOf(diff, nums[i] - nums[i - k + 1])
    }
    return diff
}

// Iterate the minimum element from `0` to `nums.size - k`
fun minimumDifference(nums: IntArray, k: Int): Int {
    nums.sort()
    var diff = Int.MAX_VALUE
    for (i in 0..nums.size - k) {
        diff = minOf(diff, nums[i + k - 1] - nums[i])
    }
    return diff
}