Skip to content

3774. Absolute Difference Between Maximum and Minimum K Elements

SourceWeekly Contest 480 Q1DifficultyEasyRating1206

Description

You are given an integer array nums and an integer k.

Find the absolute difference between:

  • the sum of the k largest elements in the array; and
  • the sum of the k smallest elements in the array.

Return an integer denoting this difference.

 

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 <= n == nums.length <= 100
  • 1 <= nums[i] <= 100
  • 1 <= k <= n

Solutions

Solution 1: Sorting

Thinking

The gap between the sum of the \(k\) largest and the \(k\) smallest values is, after sorting, the last \(k\) entries minus the first \(k\). With \(n\le 100\) a full sort is enough.

We first sort the array \(\textit{nums}\). Then we calculate the sum of the first \(k\) elements and the sum of the last \(k\) elements in the array, and finally return the difference between them.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\), where \(n\) is the length of the array \(\textit{nums}\).

1
2
3
4
class Solution:
    def absDifference(self, nums: List[int], k: int) -> int:
        nums.sort()
        return sum(nums[-k:]) - sum(nums[:k])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int absDifference(int[] nums, int k) {
        Arrays.sort(nums);
        int ans = 0;
        int n = nums.length;
        for (int i = 0; i < k; ++i) {
            ans += nums[n - i - 1] - nums[i];
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int absDifference(vector<int>& nums, int k) {
        ranges::sort(nums);
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < k; ++i) {
            ans += nums[n - i - 1] - nums[i];
        }
        return ans;
    }
};

1
2
3
4
5
6
7
func absDifference(nums []int, k int) (ans int) {
    slices.Sort(nums)
    for i := 0; i < k; i++ {
        ans += nums[len(nums)-i-1] - nums[i]
    }
    return
}

1
2
3
4
5
6
7
8
function absDifference(nums: number[], k: number): number {
    nums.sort((a, b) => a - b);
    let ans = 0;
    for (let i = 0; i < k; ++i) {
        ans += nums.at(-i - 1)! - nums[i];
    }
    return ans;
}

Comments