Absolute Difference Between Maximum and Minimum K Elements - Solution & Explanation

Problem Overview: Given an integer array and an integer k, compute the absolute difference between the k-th smallest element and the k-th largest element. The task reduces to identifying order statistics in the array and measuring the distance between those two values.

Approach 1: Sorting (O(n log n) time, O(1) or O(n) space)

Sort the array in non‑decreasing order using a standard sorting algorithm. After sorting, the k‑th smallest element sits at index k-1 and the k‑th largest element sits at index n-k. The answer becomes abs(nums[n-k] - nums[k-1]). This works because sorting places all values in rank order, so positional indexing directly gives the required order statistics. The implementation is simple and reliable, making it the most practical solution for this problem.

Sorting also integrates cleanly with standard library functions in most languages. You perform one sort operation, read the two positions, and compute the difference. Since arrays are already the underlying data structure, no additional structures are required beyond what the sort implementation uses internally. This makes it a natural solution when working with arrays and rank‑based queries.

Approach 2: Selection (Quickselect / Heap) (Average O(n) time, O(1)–O(k) space)

Instead of fully sorting the array, you can compute order statistics directly. Algorithms like Quickselect find the k‑th smallest element in average O(n) time. Run it twice: once to find the k‑th smallest value and once to find the k‑th largest (or equivalently the (n-k+1)-th smallest). Another alternative is using two heaps: a min‑heap for the largest k elements and a max‑heap for the smallest k elements. These methods avoid sorting the entire dataset and focus only on the elements needed for the calculation.

This approach becomes useful when the array is very large and only a few order statistics are required. It leverages selection algorithms rather than full sorting, reducing average runtime to linear time. The tradeoff is slightly more complex code and edge‑case handling compared to the straightforward sort solution.

Recommended for interviews: The sorting approach is usually expected. It shows clear reasoning and produces an O(n log n) solution with minimal code. Mentioning Quickselect as a possible O(n) optimization demonstrates deeper understanding, but implementing sorting first communicates correctness and clarity under interview time constraints.