BackhardHeap

Kth Smallest Absolute Difference Solution

Problem Statement

Given an array of integers, find the kth smallest absolute difference between any two elements in the array.

Example 1
Input
arr = [17, 23, 29, 31], k = 3
Output
6

Explanation: The absolute differences are |17-23| = 6, |17-29| = 12, |17-31| = 14, |23-29| = 6, |23-31| = 8, |29-31| = 2. The 3rd smallest absolute difference is 6.

Example 2
Input
arr = [5, 8, 12, 18], k = 2
Output
4

Explanation: The absolute differences are |5-8| = 3, |5-12| = 7, |5-18| = 13, |8-12| = 4, |8-18| = 10, |12-18| = 6. The 2nd smallest absolute difference is 4.

Constraints

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^6
  • 1 <= k <= arr.length*(arr.length-1)/2

More Heap Problems

Segmented Node ClustereasySegmented Subsequence SumeasySegmented Interval PartitioneasySegmented Range Extenteasy
View all problems →
Live Compiler
Loading...
Test Cases & Output
🔒 Sign up to run your code

🚀 Practice this problem

Run code, get AI hints & track streak

Sign Up Free