Absolute Difference Between Maximum and Minimum K Elements Python/Java solution

In Python or Java, sort the array using the built-in sort method. Then read nums[k-1] for the k-th smallest and nums[n-k] for the k-th largest element. Return the absolute difference between them. This implementation runs in O(n log n) time.

What is the best approach for Absolute Difference Between Maximum and Minimum K Elements?

The most practical approach is sorting the array. After sorting, the k-th smallest element is at index k-1 and the k-th largest is at index n-k. Compute the absolute difference between these two values. This solution runs in O(n log n) time and requires minimal code.

Is Absolute Difference Between Maximum and Minimum K Elements asked at Google/Amazon/Meta?

Problems involving order statistics, sorting, and array ranking frequently appear in interviews at companies like Amazon, Google, and Meta. Variants often ask for k-th smallest, k-th largest, or differences between ranked elements. Understanding sorting and Quickselect helps solve many of these questions.

What data structure is used in Absolute Difference Between Maximum and Minimum K Elements?

The core data structure is an array. The main algorithmic tool is sorting, though heaps or Quickselect can also be used to find the required order statistics. Heaps are especially useful when tracking the top or bottom k elements efficiently.

What is the time complexity of Absolute Difference Between Maximum and Minimum K Elements?

Using the standard sorting solution, the time complexity is O(n log n) because the array must be sorted first. The final lookup and difference calculation take constant time. Space complexity depends on the sorting implementation and is typically O(1) to O(n).

Description Hints 1 Solution Video 2:32

3774. Absolute Difference Between Maximum and Minimum K Elements

Q: Is Absolute Difference Between Maximum and Minimum K Elements easy or hard?

The problem is typically categorized as Easy because the straightforward solution uses sorting and simple indexing. Once the array is sorted, identifying the k-th smallest and k-th largest elements is trivial. The challenge mainly tests understanding of array ordering and indexing.

Q: How to solve Absolute Difference Between Maximum and Minimum K Elements in O(n)?

Use a selection algorithm such as Quickselect to find order statistics directly. Quickselect can find the k-th smallest element in average O(n) time. Running it for both the k-th smallest and the k-th largest elements avoids sorting the entire array and keeps the overall complexity linear on average.

Easy74.8% acceptance

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

Topics

Array Sorting

Hints open one at a time

Hint 1

Sort the array and find the difference between the first and last k values.

2:32

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

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

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[5,2,2,4]
2

Input

[100]
1

Your code is saved on this device.Solution