3774. Absolute Difference Between Maximum and Minimum K Elements

EasyArraySorting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

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

Your task is to find the absolute difference between two values:

The sum of the k largest elements in the array.
The sum of the k smallest elements in the array.

In other words, you need to:

Identify the k largest elements and add them together.
Identify the k smallest elements and add them together.
Compute the difference between these two sums.

Return an integer denoting this difference.

Since the k largest elements always have a sum greater than or equal to the sum of the k smallest elements, the difference is naturally non-negative.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Binary Search?

This problem maps to Binary Search through a short path in the full flowchart.

Sorting the array makes it direct to pick the k smallest from the front and k largest from the back in O(n log n) time.

Open in Flowchart

Intuition

To find the k largest and k smallest elements, the most straightforward idea is to sort the array first.

Once the array is sorted in ascending order:

The k smallest elements are simply the first k elements, i.e., nums[:k].
The k largest elements are simply the last k elements, i.e., nums[-k:].

After sorting, we no longer need to search for these elements manually—their positions are fixed at the two ends of the array. We just take the sum of each group and compute their difference.

Since the array is sorted, the sum of the last k elements is always greater than or equal to the sum of the first k elements. This means subtracting the smaller sum from the larger sum directly gives us a non-negative result, so we don't even need to wrap it in an absolute value function.

Pattern Learn more about Sorting patterns.

Solution Approach

Solution 1: Sorting

We first sort the array nums in ascending order. After sorting, the smallest elements are positioned at the front of the array, while the largest elements are positioned at the back.

Then we compute two sums:

The sum of the last k elements nums[-k:], which represents the sum of the k largest elements.
The sum of the first k elements nums[:k], which represents the sum of the k smallest elements.

Finally, we return the difference between these two sums: sum(nums[-k:]) - sum(nums[:k]).

The implementation uses Python's built-in sort() method to sort the array, and slicing combined with sum() to extract and add up the relevant elements.

The time complexity is O(n × log n), where n is the length of the array nums. This is dominated by the sorting step. The space complexity is O(log n), which accounts for the stack space used during sorting.

Example Walkthrough

Let's trace through the solution with a small example:

Input: nums = [7, 2, 9, 4, 1], k = 2

Step 1: Sort the array in ascending order

We begin by sorting nums so the smallest values move to the front and the largest values move to the back.

Original: [7, 2, 9, 4, 1]
Sorted:   [1, 2, 4, 7, 9]

Now the array's structure is predictable: the smallest elements are on the left end, and the largest are on the right end.

Step 2: Identify and sum the k largest elements

With k = 2, the 2 largest elements are the last 2 elements of the sorted array, accessed via nums[-k:]:

nums[-2:] = [7, 9]
sum = 7 + 9 = 16

Step 3: Identify and sum the k smallest elements

The 2 smallest elements are the first 2 elements of the sorted array, accessed via nums[:k]:

nums[:2] = [1, 2]
sum = 1 + 2 = 3

Step 4: Compute the difference

Because the array is sorted, the sum of the largest elements (16) is guaranteed to be greater than or equal to the sum of the smallest elements (3). So we can subtract directly without needing an absolute value:

result = 16 - 3 = 13

Output: 13

This confirms the approach: a single sort fixes the positions of the relevant elements at both ends of the array, allowing us to grab them with simple slicing and compute the answer in one clean subtraction.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def absDifference(self, nums: List[int], k: int) -> int:
6        # Sort the array in ascending order so the smallest values come first
7        # and the largest values come last.
8        nums.sort()
9
10        # Sum of the k largest elements (the last k items after sorting).
11        sum_of_largest = sum(nums[-k:])
12
13        # Sum of the k smallest elements (the first k items after sorting).
14        sum_of_smallest = sum(nums[:k])
15
16        # The difference between the largest-k sum and the smallest-k sum.
17        return sum_of_largest - sum_of_smallest
18

1class Solution {
2    /**
3     * Calculates the sum of differences between the largest and smallest
4     * elements, paired from the outermost towards the center, for k pairs.
5     *
6     * @param nums the input array of integers
7     * @param k    the number of outer pairs to consider
8     * @return the accumulated absolute difference for the first k pairs
9     */
10    public int absDifference(int[] nums, int k) {
11        // Sort the array in ascending order so the smallest values are at the
12        // front and the largest values are at the back.
13        Arrays.sort(nums);
14
15        int sum = 0;
16        int length = nums.length;
17
18        // For each of the k pairs, add the difference between the i-th largest
19        // element (from the end) and the i-th smallest element (from the front).
20        for (int i = 0; i < k; i++) {
21            int largest = nums[length - i - 1];
22            int smallest = nums[i];
23            sum += largest - smallest;
24        }
25
26        return sum;
27    }
28}
29

1class Solution {
2public:
3    int absDifference(vector<int>& nums, int k) {
4        // Sort the array in ascending order so the smallest and largest
5        // elements can be accessed from both ends.
6        ranges::sort(nums);
7
8        int n = static_cast<int>(nums.size());
9        int ans = 0;
10
11        // Pair the k largest elements with the k smallest elements.
12        // For each iteration i:
13        //   - nums[n - i - 1] is the (i+1)-th largest element
14        //   - nums[i]         is the (i+1)-th smallest element
15        // Their difference is guaranteed to be non-negative because the
16        // array is sorted, so it equals the absolute difference.
17        for (int i = 0; i < k; ++i) {
18            ans += nums[n - i - 1] - nums[i];
19        }
20
21        return ans;
22    }
23};
24

1/**
2 * Computes the sum of absolute differences between the k largest
3 * and the k smallest elements of the array.
4 *
5 * After sorting the array in ascending order, we pair the i-th
6 * smallest element with the i-th largest element (for i in [0, k))
7 * and accumulate the difference (largest - smallest) for each pair.
8 *
9 * @param nums - The input array of numbers.
10 * @param k    - The number of smallest/largest element pairs to consider.
11 * @returns The accumulated absolute difference.
12 */
13function absDifference(nums: number[], k: number): number {
14    // Sort the array in ascending order so the smallest values are at
15    // the front and the largest values are at the back.
16    nums.sort((a, b) => a - b);
17
18    // Accumulator for the total difference.
19    let ans = 0;
20
21    // Pair the i-th smallest element with the i-th largest element
22    // and add their difference to the result.
23    for (let i = 0; i < k; ++i) {
24        // nums.at(-i - 1) accesses the i-th element from the end (largest),
25        // while nums[i] is the i-th element from the start (smallest).
26        ans += nums.at(-i - 1)! - nums[i];
27    }
28
29    // Return the total accumulated difference.
30    return ans;
31}
32

Time and Space Complexity

Time Complexity: O(n × log n), where n is the length of the array nums. The dominant operation is nums.sort(), which uses Timsort and requires O(n × log n) time. The subsequent slicing operations nums[-k:] and nums[:k], along with their sum computations, each take O(k) time, which is bounded by O(n) and therefore does not exceed the sorting cost.
Space Complexity: O(log n), where n is the length of the array nums. The sorting algorithm (Timsort) requires O(log n) space for its recursive/stack overhead. The slicing operations create new lists of size O(k); if this auxiliary space is counted, it would add O(k) (bounded by O(n)), but following the reference answer, the space complexity is taken as O(log n) from the sorting overhead.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Mishandling the case when `k` is large relative to the array length

A frequent mistake occurs when 2 * k > len(nums), meaning the k largest and k smallest elements overlap. In this scenario, some elements get counted in both the "largest" and "smallest" groups.

Why this is a problem:

With slicing like nums[-k:] and nums[:k], if k exceeds half the array length, the two slices share common elements. For example, given nums = [1, 2, 3] and k = 2:

nums[-2:] → [2, 3], sum = 5
nums[:2] → [1, 2], sum = 3
Difference = 5 - 3 = 2

Here the element 2 is double-counted across both groups. Depending on the intended problem semantics, this may or may not be correct.

Two perspectives on the intended behavior:

Overlap is allowed (the slices are independent selections). The original code is correct, since nums[-k:] and nums[:k] are computed independently. This is the most common interpretation for this kind of problem.
Overlap should be disallowed (each element used at most once). Then you must guard against 2 * k > len(nums):

from typing import List


class Solution:
    def absDifference(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # Guard: ensure the two groups do not overlap.
        if 2 * k > n:
            raise ValueError("k is too large; largest and smallest groups overlap")

        nums.sort()
        return sum(nums[-k:]) - sum(nums[:k])

Pitfall 2: The destructive side effect of `nums.sort()`

nums.sort() sorts the array in place, mutating the caller's original list. If the caller relies on the original ordering afterward, this introduces a subtle bug.

Solution: Use sorted() to create a new sorted list instead of mutating the input:

from typing import List


class Solution:
    def absDifference(self, nums: List[int], k: int) -> int:
        # sorted() returns a new list and preserves the original ordering of nums.
        ordered = sorted(nums)
        return sum(ordered[-k:]) - sum(ordered[:k])

Pitfall 3: Assuming the difference is always non-negative without verification

The problem states the difference is naturally non-negative because the k largest elements sum to at least the k smallest. While true under correct selection, if you accidentally swap the slices (e.g., nums[:k] - nums[-k:]), you'll produce a negative result.

Solution: Wrap the result in abs() to defensively guarantee non-negativity, regardless of slice ordering:

return abs(sum(ordered[-k:]) - sum(ordered[:k]))

This makes the intent explicit and protects against accidental slice swaps.

Pitfall 4: Not validating `k` against the array bounds

If k == 0, then nums[-0:] becomes nums[0:] (the entire array) rather than an empty slice, since nums[-0:] is equivalent to nums[0:]. This is a classic Python slicing gotcha.

Solution: Handle the k == 0 edge case explicitly:

from typing import List


class Solution:
    def absDifference(self, nums: List[int], k: int) -> int:
        if k == 0:
            return 0
        ordered = sorted(nums)
        return abs(sum(ordered[-k:]) - sum(ordered[:k]))

This avoids the nums[-0:] trap that would otherwise sum the full array as the "largest" group.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which of these pictures shows the visit order of a depth-first search?

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering