We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Difference Between Highest and Lowest of K Scores

Number: 2112

Difficulty: Easy

Paid? No

Companies: Tinkoff, Google, Amazon, Meta

Problem Description

Given an array of scores and an integer k, select any k scores such that the difference between the highest and the lowest score in the selection is minimized. Return this minimum possible difference.

Key Insights

  • Sorting the array simplifies the problem since the minimum difference among k scores will be found in a contiguous subarray.
  • A sliding window approach of size k on the sorted array allows us to efficiently evaluate each candidate set.
  • Compute the difference between the first and last elements in each window, and track the minimum difference found.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the array. Space Complexity: O(1) if sorting is done in-place, otherwise O(n) for the sorted copy.

Solution

Sort the input array first to line up scores in non-decreasing order. Then, use a sliding window of size k to evaluate every contiguous block of k elements in the sorted array. In each block, the difference between the maximum (last element) and minimum (first element) is computed. The minimum of these differences over all possible windows is the answer. This approach efficiently leverages the sorted order to simplify the evaluation of potential candidate sets.

Code Solutions

def minimum_difference(nums, k):
    # Sort the scores list to evaluate contiguous groups easily.
    nums.sort()
    # Set initial answer to infinity for comparison.
    min_diff = float('inf')
    # Iterate over all possible windows of size k.
    for i in range(len(nums) - k + 1):
        # Compute difference between the max and min in this window.
        current_diff = nums[i + k - 1] - nums[i]
        # Update the minimum difference found.
        min_diff = min(min_diff, current_diff)
    return min_diff

# Example usage:
print(minimum_difference([9, 4, 1, 7], 2))  # Expected output: 2
← Back to All Questions