Absolute Difference Between Maximum and Minimum K Elements

Difficulty: Easy | Acceptance: 75.60% | Paid: No Topics: Array, Sorting

You are given an integer array nums and an integer k. You need to select k elements from nums such that the absolute difference between the maximum and minimum of the selected elements is minimized. Return that minimum absolute difference.

• Examples
• Constraints
• Approach 1: Sorting
• Approach 2: Brute Force

Examples

Example 1

Input:

nums = [5,2,2,4], k = 2

Output:

5

Explanation: The k = 2 largest elements are 4 and 5. Their sum is 4 + 5 = 9.

The k = 2 smallest elements are 2 and 2. Their sum is 2 + 2 = 4.

The absolute difference is abs(9 - 4) = 5.

Example 2

Input:

nums = [100], k = 1

Output:

0

Explanation: The largest element is 100.

The smallest element is 100.

The absolute difference is abs(100 - 100) = 0.

Constraints

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

Approach 1: Sorting

Intuition To minimize the difference between the maximum and minimum elements in a subset of size k, the elements should be as close to each other as possible in value. Sorting the array brings close values together, allowing us to check contiguous windows of size k to find the smallest range.

Steps

• Sort the array nums in ascending order.
• Initialize min_diff to a large value (e.g., infinity).
• Iterate through the sorted array from index 0 to n - k.
• For each index i, calculate the difference between nums[i + k - 1] (the max in the current window) and nums[i] (the min in the current window).
• Update min_diff if the current difference is smaller.
• Return min_diff.

class Solution:
    def minimumDifference(self, nums: list[int], k: int) -> int:
        nums.sort()
        min_diff = float('inf')
        for i in range(len(nums) - k + 1):
            diff = nums[i + k - 1] - nums[i]
            if diff < min_diff:
                min_diff = diff
        return min_diff

Complexity

• Time: O(N log N) due to the sorting step, where N is the length of nums. The sliding window part is O(N).
• Space: O(1) or O(N) depending on the sorting algorithm’s space complexity.
• Notes: This is the most efficient approach for the given constraints.

Approach 2: Brute Force

Intuition Check every possible combination of k elements in the array to find the one with the smallest range. This approach directly implements the problem definition without optimization.

Steps

• Generate all possible subsets of size k from nums.
• For each subset, find the maximum and minimum values.
• Calculate the absolute difference (max - min).
• Track the minimum difference found across all subsets.
• Return the result.

from itertools import combinations

class Solution:
    def minimumDifference(self, nums: list[int], k: int) -> int:
        min_diff = float('inf')
        for combo in combinations(nums, k):
            diff = max(combo) - min(combo)
            if diff < min_diff:
                min_diff = diff
        return min_diff

Complexity

• Time: O(N choose k) * k, which is exponential and extremely inefficient for large N.
• Space: O(k) for the recursion stack or storing the current combination.
• Notes: This approach is included for conceptual understanding but will result in a Time Limit Exceeded (TLE) error for large inputs due to high complexity.