LeetCode 3774 - Absolute Difference Between Maximum and Minimum K Elements

LeetCode Problem 3774

Difficulty: 🟢 Easy
Topics: Array, Sorting

Solution

Problem Understanding

The problem asks us to calculate the absolute difference between the sum of the k largest elements and the sum of the k smallest elements in a given array nums. In other words, we first need to identify the k smallest values, sum them up, then identify the k largest values, sum them, and finally compute the absolute difference between these two sums.

The input consists of an array of integers nums with length n and an integer k. The constraints indicate that the array length is relatively small, up to 100 elements, and all integers are positive and at most 100. This tells us that operations like sorting the entire array are feasible without performance issues. The value k is guaranteed to be at least 1 and at most n, so we do not have to handle invalid k values.

Important edge cases include when the array has only one element, which means the largest and smallest elements are identical, resulting in an absolute difference of zero. Another edge case is when all elements in the array are the same, so the largest and smallest sums are equal. Also, k could be equal to n, which would mean summing the entire array for both the largest and smallest sums.

Approaches

The brute-force approach involves explicitly finding all combinations of k largest and smallest elements. We could use nested loops or maintain a selection of all possible k-element subsets to compute the sums. While this guarantees correctness, it is inefficient because enumerating combinations has combinatorial time complexity, which grows exponentially with n. For n = 100 and k = 50, this approach is clearly infeasible.

The key insight for an optimal solution is that we do not need to generate all combinations. Instead, sorting the array simplifies the problem: the first k elements of the sorted array are the smallest, and the last k elements are the largest. Summing these k elements directly gives the required sums, and computing the absolute difference becomes trivial. Sorting takes O(n log n) time, which is acceptable for the given constraints, and the sum calculations take O(k) time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n choose k)	O(k)	Generate all k-element subsets, compute sums
Optimal	O(n log n)	O(1)	Sort array, sum first k and last k elements

Algorithm Walkthrough

1. Begin by sorting the array nums in ascending order. Sorting ensures that the smallest elements appear first and the largest elements appear last.
2. Initialize a variable smallest_sum and compute the sum of the first k elements of the sorted array. These are guaranteed to be the k smallest elements.
3. Initialize a variable largest_sum and compute the sum of the last k elements of the sorted array. These are guaranteed to be the k largest elements.
4. Compute the absolute difference between largest_sum and smallest_sum using the built-in absolute value function.
5. Return the resulting absolute difference as the final answer.

Why it works: Sorting guarantees that the first k elements are the smallest and the last k elements are the largest. Summing these subsets directly and taking the absolute difference correctly computes the required value. This approach leverages the sorted order to avoid unnecessary combinations, providing both correctness and efficiency.

Python Solution

from typing import List

class Solution:
    def absDifference(self, nums: List[int], k: int) -> int:
        nums.sort()
        smallest_sum = sum(nums[:k])
        largest_sum = sum(nums[-k:])
        return abs(largest_sum - smallest_sum)

This implementation first sorts nums, then calculates smallest_sum by summing the first k elements and largest_sum by summing the last k elements. Finally, it returns the absolute difference. Each step directly maps to the algorithm walkthrough above and handles all edge cases automatically.

Go Solution

import "sort"
import "math"

func absDifference(nums []int, k int) int {
    sort.Ints(nums)
    smallestSum := 0
    largestSum := 0
    n := len(nums)
    
    for i := 0; i < k; i++ {
        smallestSum += nums[i]
        largestSum += nums[n-1-i]
    }
    
    return int(math.Abs(float64(largestSum - smallestSum)))
}

In Go, we sort the slice using sort.Ints. We then iterate k times, adding to smallestSum from the start and to largestSum from the end of the slice. Go requires converting the integer difference to float64 for math.Abs and back to int, since math.Abs operates on floats.

Worked Examples

Example 1: nums = [5,2,2,4], k = 2

Step	Sorted Array	smallest_sum	largest_sum	Absolute Difference
Initial	[5,2,2,4]	-	-	-
Sort	[2,2,4,5]	-	-	-
Sum first 2	-	2+2=4	-	-
Sum last 2	-	-	4+5=9	-
Compute abs	-	-	-	abs(9-4)=5

Example 2: nums = [100], k = 1

Step	Sorted Array	smallest_sum	largest_sum	Absolute Difference
Initial	[100]	-	-	-
Sort	[100]	-	-	-
Sum first 1	-	100	-	-
Sum last 1	-	-	100	-
Compute abs	-	-	-	abs(100-100)=0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime; summing k elements is O(k) which is ≤ O(n)
Space	O(1)	Sorting in-place and storing sums requires constant extra space

The complexity is dominated by sorting the array. The subsequent sum calculations are linear in k, but since k ≤ n, they do not affect the overall asymptotic complexity.

Test Cases

# provided examples
assert Solution().absDifference([5,2,2,4], 2) == 5  # Example 1
assert Solution().absDifference([100], 1) == 0      # Example 2

# all elements equal
assert Solution().absDifference([7,7,7,7], 2) == 0  # sums are equal

# k equals array length
assert Solution().absDifference([1,2,3,4,5], 5) == 0  # sums of all elements are equal

# k = 1, multiple distinct elements
assert Solution().absDifference([3,1,4,2], 1) == 3  # largest 4, smallest 1

# array has repeated elements
assert Solution().absDifference([1,2,2,3,3,4], 3) == 6  # largest 4+3+3=10, smallest 1+2+2=5

Test	Why
[5,2,2,4], 2	validates normal behavior with distinct and duplicate numbers
[100], 1	smallest possible array, k=1
[7,7,7,7], 2	all elements equal, sum difference zero
[1,2,3,4,5], 5	k equals array length
[3,1,4,2], 1	k=1, smallest vs largest element
[1,2,2,3,3,4], 3	duplicates in array affecting sums

Edge Cases

An important edge case is when the array has only one element. In this situation, the largest and smallest sums are the same, and the absolute difference should be zero. This is automatically handled by the algorithm since sorting and summing still work.

Another edge case occurs when all elements in the array are identical. No matter what k is chosen, the sum of the k largest elements equals the sum of the k smallest elements, so the absolute difference is zero. Sorting preserves the order, and summing the first and last k elements naturally produces the same value.

A third edge case is when k equals the length of the array. In this scenario, summing the first k elements and the last k elements sums the entire array in both cases, resulting again in an absolute difference of zero. The algorithm handles this correctly because slicing in Python or iterating in Go with k = n correctly covers all elements.