3774. Absolute Difference Between Maximum and Minimum K Elements
Problem Statement
You are given an integer array nums and an integer k.
Find the absolute difference between:
- The sum of the
klargest elements in the array; and - The sum of the
ksmallest 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.
Visualization
For nums = [5,2,2,4], k = 2:
Smallest k = 2: 2 + 2 = 4
Largest k = 2: 4 + 5 = 9
Difference: |9 - 4| = 5
Key Insight
The solution requires finding two distinct sums from the same array:
- Sum of k smallest elements: The k elements with minimum values
- Sum of k largest elements: The k elements with maximum values
Important observations:
- The same element cannot be counted in both sums (unless the array has duplicates and k is large)
- When k = n (array length), both sums include all elements, so the difference is 0
- The absolute difference ensures a non-negative result
- With small constraints (n ≤ 100), even O(n²) approaches would work, but we aim for optimal solutions
Approach 1: Sorting and Direct Summation (Optimal for Given Constraints)
Sort the array and directly sum the first k elements (smallest) and last k elements (largest), then compute their absolute difference.
Algorithm Steps
- Sort the array in non-decreasing order
- Calculate sum of first k elements (smallest)
- Calculate sum of last k elements (largest)
- Return absolute difference between the two sums
How It Works
After sorting, the smallest k elements are at indices 0 to k-1, and the largest k elements are at indices n-k to n-1. We sum these ranges directly.
Complexity Analysis
| Time Complexity | Space Complexity |
|---|---|
| O(n log n) | O(1) or O(log n) for sorting algorithm |
Where n is the length of nums array. The dominant factor is sorting. Built-in sort typically uses O(log n) space for recursion or O(1) for iterative sorts.
class Solution {
public:
int absDifference(vector<int>& nums, int k) {
int n = nums.size();
// Sort the array in non-decreasing order
sort(begin(nums), end(nums));
// Calculate sum of k smallest elements (first k)
int sumSmallest = accumulate(begin(nums), begin(nums) + k, 0);
// Calculate sum of k largest elements (last k)
int sumLargest = accumulate(end(nums) - k, end(nums), 0);
// Return absolute difference
return abs(sumLargest - sumSmallest);
}
};import java.util.*;
class Solution {
public int absDifference(int[] nums, int k) {
int n = nums.length;
// Sort the array in non-decreasing order
Arrays.sort(nums);
// Calculate sum of k smallest elements (first k)
int sumSmallest = 0;
for (int i = 0; i < k; i++) {
sumSmallest += nums[i];
}
// Calculate sum of k largest elements (last k)
int sumLargest = 0;
for (int i = n - k; i < n; i++) {
sumLargest += nums[i];
}
// Return absolute difference
return Math.abs(sumLargest - sumSmallest);
}
}class Solution:
def absDifference(self, nums: list[int], k: int) -> int:
n = len(nums)
# Sort the array in non-decreasing order
nums.sort()
# Calculate sum of k smallest elements (first k)
sum_smallest = sum(nums[:k])
# Calculate sum of k largest elements (last k)
sum_largest = sum(nums[-k:])
# Return absolute difference
return abs(sum_largest - sum_smallest)Approach 2: Heap-Based Selection (O(n log k) Time)
Use a max-heap to find k smallest elements and a min-heap to find k largest elements without fully sorting the array.
Algorithm Steps
- For k smallest elements:
- Use a max-heap (priority queue) of size k
- Add each element, removing largest when heap size > k
- Remaining heap contains k smallest elements
- For k largest elements:
- Use a min-heap (priority queue) of size k
- Add each element, removing smallest when heap size > k
- Remaining heap contains k largest elements
- Sum elements in both heaps and compute absolute difference
How It Works
A max-heap keeps track of the largest among the smallest k elements seen so far. When we see a smaller element, it replaces the current largest in the heap. Similarly, a min-heap keeps track of the smallest among the largest k elements.
Complexity Analysis
| Time Complexity | Space Complexity |
|---|---|
| O(n log k) | O(k) |
We process n elements, performing O(log k) heap operations for each. Space is O(k) for storing the heaps.
class Solution {
public:
int absDifference(vector<int>& nums, int k) {
// Max-heap for k smallest elements (we want to keep smallest, so remove largest)
priority_queue<int> maxHeap; // default is max-heap
// Min-heap for k largest elements (we want to keep largest, so remove smallest)
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int num : nums) {
// Process for k smallest (max-heap)
maxHeap.push(num);
if (maxHeap.size() > k) {
maxHeap.pop(); // Remove the largest (root of max-heap)
}
// Process for k largest (min-heap)
minHeap.push(num);
if (minHeap.size() > k) {
minHeap.pop(); // Remove the smallest (root of min-heap)
}
}
// Calculate sum of k smallest elements from max-heap
int sumSmallest = 0;
while (!maxHeap.empty()) {
sumSmallest += maxHeap.top();
maxHeap.pop();
}
// Calculate sum of k largest elements from min-heap
int sumLargest = 0;
while (!minHeap.empty()) {
sumLargest += minHeap.top();
minHeap.pop();
}
return abs(sumLargest - sumSmallest);
}
};import java.util.*;
class Solution {
public int absDifference(int[] nums, int k) {
// Max-heap for k smallest elements (we want to keep smallest, so remove largest)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// Min-heap for k largest elements (we want to keep largest, so remove smallest)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
// Process for k smallest (max-heap)
maxHeap.offer(num);
if (maxHeap.size() > k) {
maxHeap.poll(); // Remove the largest (root of max-heap)
}
// Process for k largest (min-heap)
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll(); // Remove the smallest (root of min-heap)
}
}
// Calculate sum of k smallest elements from max-heap
int sumSmallest = 0;
while (!maxHeap.isEmpty()) {
sumSmallest += maxHeap.poll();
}
// Calculate sum of k largest elements from min-heap
int sumLargest = 0;
while (!minHeap.isEmpty()) {
sumLargest += minHeap.poll();
}
return Math.abs(sumLargest - sumSmallest);
}
}import heapq
class Solution:
def absDifference(self, nums: list[int], k: int) -> int:
# Max-heap for k smallest elements (we use min-heap with negative values)
max_heap = [] # Will store negatives to simulate max-heap
# Min-heap for k largest elements
min_heap = []
for num in nums:
# Process for k smallest (using negative to simulate max-heap)
heapq.heappush(max_heap, -num)
if len(max_heap) > k:
heapq.heappop(max_heap) # Remove the largest (most negative when negated)
# Process for k largest (standard min-heap)
heapq.heappush(min_heap, num)
if len(min_heap) > k:
heapq.heappop(min_heap) # Remove the smallest
# Calculate sum of k smallest elements (negate back from max-heap)
sum_smallest = sum(-x for x in max_heap)
# Calculate sum of k largest elements from min-heap
sum_largest = sum(min_heap)
return abs(sum_largest - sum_smallest)Approach 3: Quickselect Algorithm (O(n) Average Time)
Use the Quickselect algorithm to find the k smallest and k largest elements without fully sorting the array.
Algorithm Steps
- Make a copy of the array to avoid modifying the original
- Use Quickselect to find the kth smallest element and partition the array
- Sum all elements ≤ kth smallest (handling duplicates carefully)
- Similarly find kth largest and sum all elements ≥ kth largest
- Compute absolute difference
How It Works
Quickselect is a selection algorithm to find the kth smallest/largest element. It uses the same partitioning scheme as Quicksort but only recurses into one side.
Complexity Analysis
| Time Complexity | Space Complexity |
|---|---|
| O(n) average, O(n²) worst-case | O(1) or O(log n) for recursion |
Average case is linear time. Worst-case is quadratic but can be avoided with randomized pivot selection.
class Solution {
public:
// Helper function for Quickselect
int partition(vector<int>& nums, int left, int right, int pivotIndex) {
int pivotValue = nums[pivotIndex];
swap(nums[pivotIndex], nums[right]); // Move pivot to end
int storeIndex = left;
for (int i = left; i < right; i++) {
if (nums[i] < pivotValue) {
swap(nums[storeIndex], nums[i]);
storeIndex++;
}
}
swap(nums[right], nums[storeIndex]); // Move pivot to its final place
return storeIndex;
}
// Quickselect to find kth smallest element
int quickselect(vector<int>& nums, int left, int right, int k) {
if (left == right) return nums[left];
// Random pivot for better average performance
int pivotIndex = left + rand() % (right - left + 1);
pivotIndex = partition(nums, left, right, pivotIndex);
if (k == pivotIndex) {
return nums[k];
} else if (k < pivotIndex) {
return quickselect(nums, left, pivotIndex - 1, k);
} else {
return quickselect(nums, pivotIndex + 1, right, k);
}
}
int absDifference(vector<int>& nums, int k) {
int n = nums.size();
// Make copies for finding smallest and largest
vector<int> numsForSmallest = nums;
vector<int> numsForLargest = nums;
// Find kth smallest element
int kthSmallest = quickselect(numsForSmallest, 0, n - 1, k - 1);
// Find kth largest element (which is (n-k)th smallest)
int kthLargest = quickselect(numsForLargest, 0, n - 1, n - k);
// Sum k smallest elements
int sumSmallest = 0;
for (int num : nums) {
if (num < kthSmallest) {
sumSmallest += num;
}
}
// Count how many elements equal to kthSmallest we need to include
int countKthSmallest = 0;
for (int num : nums) {
if (num == kthSmallest) countKthSmallest++;
}
// Add remaining elements equal to kthSmallest to reach k total
int needed = k;
for (int num : nums) {
if (num < kthSmallest) needed--;
}
sumSmallest += needed * kthSmallest;
// Sum k largest elements
int sumLargest = 0;
for (int num : nums) {
if (num > kthLargest) {
sumLargest += num;
}
}
// Count how many elements equal to kthLargest we need to include
int countKthLargest = 0;
for (int num : nums) {
if (num == kthLargest) countKthLargest++;
}
// Add remaining elements equal to kthLargest to reach k total
needed = k;
for (int num : nums) {
if (num > kthLargest) needed--;
}
sumLargest += needed * kthLargest;
return abs(sumLargest - sumSmallest);
}
};import java.util.*;
class Solution {
private int partition(int[] nums, int left, int right, int pivotIndex) {
int pivotValue = nums[pivotIndex];
// Move pivot to end
int temp = nums[pivotIndex];
nums[pivotIndex] = nums[right];
nums[right] = temp;
int storeIndex = left;
for (int i = left; i < right; i++) {
if (nums[i] < pivotValue) {
temp = nums[storeIndex];
nums[storeIndex] = nums[i];
nums[i] = temp;
storeIndex++;
}
}
// Move pivot to its final place
temp = nums[right];
nums[right] = nums[storeIndex];
nums[storeIndex] = temp;
return storeIndex;
}
private int quickselect(int[] nums, int left, int right, int k) {
if (left == right) return nums[left];
Random random = new Random();
int pivotIndex = left + random.nextInt(right - left + 1);
pivotIndex = partition(nums, left, right, pivotIndex);
if (k == pivotIndex) {
return nums[k];
} else if (k < pivotIndex) {
return quickselect(nums, left, pivotIndex - 1, k);
} else {
return quickselect(nums, pivotIndex + 1, right, k);
}
}
public int absDifference(int[] nums, int k) {
int n = nums.length;
// Make copies for finding smallest and largest
int[] numsForSmallest = nums.clone();
int[] numsForLargest = nums.clone();
// Find kth smallest element
int kthSmallest = quickselect(numsForSmallest, 0, n - 1, k - 1);
// Find kth largest element (which is (n-k)th smallest)
int kthLargest = quickselect(numsForLargest, 0, n - 1, n - k);
// Sum k smallest elements
int sumSmallest = 0;
for (int num : nums) {
if (num < kthSmallest) {
sumSmallest += num;
}
}
// Count how many elements equal to kthSmallest we need to include
int countKthSmallest = 0;
for (int num : nums) {
if (num == kthSmallest) countKthSmallest++;
}
// Add remaining elements equal to kthSmallest to reach k total
int needed = k;
for (int num : nums) {
if (num < kthSmallest) needed--;
}
sumSmallest += needed * kthSmallest;
// Sum k largest elements
int sumLargest = 0;
for (int num : nums) {
if (num > kthLargest) {
sumLargest += num;
}
}
// Count how many elements equal to kthLargest we need to include
int countKthLargest = 0;
for (int num : nums) {
if (num == kthLargest) countKthLargest++;
}
// Add remaining elements equal to kthLargest to reach k total
needed = k;
for (int num : nums) {
if (num > kthLargest) needed--;
}
sumLargest += needed * kthLargest;
return Math.abs(sumLargest - sumSmallest);
}
}import random
class Solution:
def partition(self, nums: list[int], left: int, right: int, pivot_index: int) -> int:
pivot_value = nums[pivot_index]
# Move pivot to end
nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
store_index = left
for i in range(left, right):
if nums[i] < pivot_value:
nums[store_index], nums[i] = nums[i], nums[store_index]
store_index += 1
# Move pivot to its final place
nums[right], nums[store_index] = nums[store_index], nums[right]
return store_index
def quickselect(self, nums: list[int], left: int, right: int, k: int) -> int:
if left == right:
return nums[left]
# Random pivot for better average performance
pivot_index = random.randint(left, right)
pivot_index = self.partition(nums, left, right, pivot_index)
if k == pivot_index:
return nums[k]
elif k < pivot_index:
return self.quickselect(nums, left, pivot_index - 1, k)
else:
return self.quickselect(nums, pivot_index + 1, right, k)
def absDifference(self, nums: list[int], k: int) -> int:
n = len(nums)
# Make copies for finding smallest and largest
nums_for_smallest = nums.copy()
nums_for_largest = nums.copy()
# Find kth smallest element
kth_smallest = self.quickselect(nums_for_smallest, 0, n - 1, k - 1)
# Find kth largest element (which is (n-k)th smallest)
kth_largest = self.quickselect(nums_for_largest, 0, n - 1, n - k)
# Sum k smallest elements
sum_smallest = 0
for num in nums:
if num < kth_smallest:
sum_smallest += num
# Count how many elements equal to kth_smallest we need to include
count_kth_smallest = nums.count(kth_smallest)
# Add remaining elements equal to kth_smallest to reach k total
needed = k
for num in nums:
if num < kth_smallest:
needed -= 1
sum_smallest += needed * kth_smallest
# Sum k largest elements
sum_largest = 0
for num in nums:
if num > kth_largest:
sum_largest += num
# Count how many elements equal to kth_largest we need to include
count_kth_largest = nums.count(kth_largest)
# Add remaining elements equal to kth_largest to reach k total
needed = k
for num in nums:
if num > kth_largest:
needed -= 1
sum_largest += needed * kth_largest
return abs(sum_largest - sum_smallest)Comparison of Approaches
| Approach | Time Complexity | Space Complexity | Key Insight | Best Use Case |
|---|---|---|---|---|
| Sorting | O(n log n) | O(1) or O(log n) | Simplest, most readable | Small n (≤100), interviews when readability matters |
| Heap-Based | O(n log k) | O(k) | Efficient when k ≪ n | Large n, small k, streaming data |
| Quickselect | O(n) avg, O(n²) worst | O(1) or O(log n) | Theoretically optimal average case | Large n, performance-critical applications |
Edge Cases and Testing
1. k = n (All Elements)
Input: nums = [1,2,3,4], k = 4 → Output: 0
Sum of k smallest = 1+2+3+4 = 10
Sum of k largest = 1+2+3+4 = 10
Difference = |10-10| = 02. k = 1 (Single Element)
Input: nums = [5,2,8,1], k = 1 → Output: 7
Smallest = 1, Largest = 8
Difference = |8-1| = 73. Duplicate Elements
Input: nums = [2,2,2,2], k = 2 → Output: 0
Smallest 2 elements: 2+2 = 4
Largest 2 elements: 2+2 = 4
Difference = |4-4| = 04. Array with Negative Numbers
Note: Problem constraints say nums[i] ≥ 1, but if negatives were allowed:
Input: nums = [-5, -2, 0, 3, 7], k = 2 → Output: 12
Smallest: -5 + -2 = -7
Largest: 3 + 7 = 10
Difference = |10 - (-7)| = 175. k Larger Than Distinct Values
Input: nums = [1,1,2,3,3], k = 4 → Output: 5
Smallest 4: 1+1+2+3 = 7
Largest 4: 1+2+3+3 = 9
Difference = |9-7| = 2FAQs
1. Why is the sorting approach optimal for this problem's constraints?
With n ≤ 100, O(n log n) sorting (approximately 100 * log₂(100) ≈ 700 operations) is extremely fast and simple to implement. More complex algorithms like quickselect have higher constant factors and implementation complexity that aren't justified for such small inputs.
2. What if the same element appears in both k smallest and k largest?
That's allowed by the problem statement. The problem asks for "the sum of the k largest elements" and "the sum of the k smallest elements" based on values, not indices. If an element value appears multiple times, it can contribute to both sums.
3. Can we use counting sort given nums[i] ≤ 100?
Yes! With values limited to 1-100, counting sort with O(n + range) = O(n + 100) = O(n) is possible. Create a frequency array of size 101, fill it, then iterate to find k smallest and largest sums.
4. What's the difference between using a max-heap vs min-heap for k smallest?
For k smallest elements, we want to keep the k smallest values seen so far. A max-heap lets us quickly remove the largest of those k when we find a smaller element. For k largest elements, a min-heap lets us quickly remove the smallest of those k when we find a larger element.
5. How does quickselect handle duplicate elements?
The standard quickselect algorithm as shown partitions elements into "less than pivot" and "greater than or equal to pivot". With duplicates, all elements equal to the pivot end up together after partitioning. We need additional logic to count how many of the pivot value to include in our sum.
6. Is there a Python one-liner solution?
Yes! Python's expressive syntax allows:
return abs(sum(sorted(nums)[-k:]) - sum(sorted(nums)[:k])). This is readable and
efficient for the given constraints.
7. What happens when k = 0?
The problem constraints state 1 ≤ k ≤ n, so k = 0 is not a valid input. If it were allowed, both sums would be 0, so the difference would be 0.
8. Can we solve this without modifying the input array?
Yes, by making a copy before sorting or using heap/quickselect approaches that don't require in-place modification of the original array. The sorting approach shown modifies the input; to avoid this, create a copy first.
9. What's the memory usage of each approach?
Sorting: O(1) or O(log n) for recursion stack. Heap: O(k) for storing heap elements. Quickselect: O(1) or O(log n) for recursion stack (can be implemented iteratively to use O(1)).
10. How would you modify the solution for very large n (e.g., 10⁷)?
For extremely large n that doesn't fit in memory, use:
1. Streaming algorithm with two heaps of size k (O(n log k) time, O(k) space)
2. If k is also large, use approximate algorithms or distributed computing
3. If data is on disk, use external sorting