Given an array of size N containing positive integers n and a number k,The absolute difference between values at indices i and j is |a[i] a[j]|. There are n*(n-1)/2 such pairs and you have to print the k_{th} smallest absolute difference among all these pairs.
 
Example 1:
Input : 
N = 4
A[] = {1, 2, 3, 4}
k = 3
Output : 
1 
Explanation :
The possible absolute differences are :
{1, 2, 3, 1, 2, 1}.
The 3rd smallest value among these is 1.
 
Example 2:
Input : 
N = 2
A[] = {10, 10}
k = 1
Output :
0
Your Task:  
You don't need to read input or print anything. Your task is to complete the function kthDiff() which takes the array A[], its size N and an integer k as inputs and returns the k_{th} smallest absolute difference among all these pairs.
 
Expected Time Complexity: O( N. (Log(N))^{2} )
Expected Auxiliary Space: O(Log(N))
 
Constraints:
1<=N<=10^{5}
1<=a[i]<=10^{5}
1 <= k <= n*(n-1)/2

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



def kthDiff( a, n, k):

    

    

    

    

Solutions:
def kthDiff(a, n, k):
	li = []
	for i in range(0, n - 1):
		for j in range(i + 1, n):
			li.append(abs(a[i] - a[j]))
	li.sort()
	return li[k - 1]


def kthDiff(nums, n, k):
	ans = []
	nums.sort()
	for i in range(len(nums)):
		for j in range(i + 1, len(nums)):
			ans.append(nums[j] - nums[i])
	return sorted(ans)[k - 1]


import heapq

def kthDiff(a, n, k):
	hp = []
	for i in range(n):
		for j in range(i + 1, n):
			heapq.heappush(hp, -abs(a[i] - a[j]))
			if len(hp) > k:
				heapq.heappop(hp)
	return -hp[0]


import bisect

def ok(a, n, mid, k):
	cnt = 0
	for i in range(n):
		cnt += n - bisect.bisect(a, a[i] + mid)
	return n * (n - 1) // 2 - cnt >= k

def kthDiff(a, n, k):
	a.sort()
	lo = min((a[i + 1] - a[i] for i in range(n - 1)))
	hi = a[-1] - a[0]
	if k >= n * (n - 1) // 2:
		return hi
	ans = -1
	while lo <= hi:
		mid = lo + (hi - lo) // 2
		if ok(a, n, mid, k):
			ans = mid
			hi = mid - 1
		else:
			lo = mid + 1
	return ans


from collections import defaultdict

def kthDiff(a, n, k):
	store = defaultdict(lambda : 0)
	for i in range(n - 1):
		for j in range(i + 1, n):
			store[abs(a[i] - a[j])] += 1
	diffs = sorted(store.keys())
	i = -1
	while k > 0:
		i += 1
		k -= store[diffs[i]]
	return diffs[i]


def kthDiff(array, n, k):
	array.sort()
	minDiff = array[1] - array[0]
	maxDiff = array[-1] - array[0]
	for i in range(1, len(array)):
		if array[i] - array[i - 1] < minDiff:
			minDiff = array[i] - array[i - 1]
	left = minDiff
	right = maxDiff
	ans = -1

	def findPair(diff):
		count = 0
		i = 0
		j = 1
		while j < len(array):
			if array[j] - array[i] <= diff:
				count += j - i
				j += 1
			else:
				i += 1
				if i == j:
					j += 1
		return count
	while left <= right:
		mid = (left + right) // 2
		if findPair(mid) >= k:
			ans = mid
			right = mid - 1
		else:
			left = mid + 1
	return ans


import heapq

def kthDiff(a, n, k):
	ans = []
	for i in range(n):
		for j in range(i + 1, n):
			ans.append(abs(a[i] - a[j]))
	ans.sort()
	return ans[k - 1]


class Solution:

	def smallestDistancePair(self, nums, k):

		def possible(guess):
			return sum((prefix[min(x + guess, W)] - prefix[x] + multiplicity[i] for (i, x) in enumerate(nums))) >= k
		nums.sort()
		W = nums[-1]
		multiplicity = [0] * len(nums)
		for (i, x) in enumerate(nums):
			if i and x == nums[i - 1]:
				multiplicity[i] = 1 + multiplicity[i - 1]
		prefix = [0] * (W + 1)
		left = 0
		for i in range(len(prefix)):
			while left < len(nums) and nums[left] == i:
				left += 1
			prefix[i] = left
		lo = 0
		hi = nums[-1] - nums[0]
		while lo < hi:
			mi = (lo + hi) // 2
			if possible(mi):
				hi = mi
			else:
				lo = mi + 1
		return lo

def kthDiff(a, n, k):
	obj = Solution()
	return obj.smallestDistancePair(a, k)


def kthDiff(A, n, k):

	def _count_le_dif(dif):
		(i, j, ans) = (0, 0, 0)
		while i < n:
			while j < n and A[j] - A[i] <= dif:
				j += 1
			ans += j - i - 1
			i += 1
		return ans
	A.sort()
	(L, R) = (0, A[n - 1] - A[0])
	while L < R:
		dif = (L + R) // 2
		if _count_le_dif(dif) < k:
			L = dif + 1
		else:
			R = dif
	return L


def kthDiff(A, n, k):

	def _count_le_mid(mid):
		(i, j, ans) = (0, 0, 0)
		while i < n:
			while j < n and A[j] - A[i] <= mid:
				j += 1
			ans += j - i - 1
			i += 1
		return ans
	A.sort()
	(L, R) = (0, A[n - 1] - A[0])
	while L < R:
		mid = (L + R) // 2
		if _count_le_mid(mid) < k:
			L = mid + 1
		else:
			R = mid
	return L


def kthDiff(a, n, k):
	diff = []
	for i in range(n):
		for j in range(i + 1, n):
			diff.append(abs(a[i] - a[j]))
	return sorted(diff)[k - 1]


def kthDiff(a, n, k):
	l = []
	a.sort()
	for i in range(n):
		for j in range(i + 1, n):
			sub = a[j] - a[i]
			l.append(sub)
	l.sort()
	return l[k - 1]


def kthDiff(a, n, k):
	b = []
	for i in range(len(a) - 1):
		for j in range(i + 1, len(a)):
			b.append(abs(a[i] - a[j]))
	b.sort()
	if len(a) == 2:
		return abs(a[0] - a[1])
	elif len(b) < k:
		return 0
	else:
		return b[k - 1]


def kthDiff(A, N, k):
	A.sort()
	l1 = []
	for i in range(N):
		l = i + 1
		while l < len(A):
			s = abs(A[i] - A[l])
			l1.append(s)
			l += 1
	l1.sort()
	res = l1[k - 1]
	return res


def kthDiff(a, n, k):
	lis = []
	a.sort()
	for i in range(n - 1):
		for j in range(i + 1, n):
			lis.append(abs(a[j] - a[i]))
	lis.sort()
	return lis[k - 1]


def sub(l):
	return abs(l[0] - l[1])

def kthDiff(a, n, k):
	dif = []
	for i in range(n):
		for j in range(i + 1, n):
			dif.append(sub([a[i], a[j]]))
	dif.sort()
	return dif[k - 1]


def kthDiff(nums, n, k):
	nums.sort()
	(lo, hi) = (0, nums[-1] - nums[0])

	def helper(mid):
		count = left = 0
		for i in range(len(nums)):
			while nums[i] - nums[left] > mid:
				left += 1
			count += i - left
		return count >= k
	while lo < hi:
		mid = (lo + hi) // 2
		if helper(mid):
			hi = mid
		else:
			lo = mid + 1
	return lo


def kthDiff(a, n, k):
	temp = []

	def pairs(i, n):
		for r in range(i + 1, n):
			temp.append(abs(a[i] - a[r]))
	for s in range(len(a)):
		pairs(s, len(a))
	temp.sort()
	return temp[k - 1]


def kthDiff(a, n, k):
	a.sort()
	new = []
	for i in range(n):
		for j in range(i + 1, n):
			new.append(a[j] - a[i])
	new.sort()
	return new[k - 1]


def kthDiff(a, n, k):
	a.sort()
	li = [0 for i in range(max(a))]
	for i in range(len(a) - 1):
		for j in range(i + 1, len(a)):
			x = a[j] - a[i]
			li[x] += 1
	sum = 0
	i = 0
	while sum < k:
		sum += li[i]
		i += 1
	return i - 1


from itertools import combinations

def kthDiff(a, n, k):
	a.sort()
	x = []
	for (i, j) in combinations(a, 2):
		x.append(j - i)
	x.sort()
	if k > len(x):
		return -1
	return x[k - 1]


def kthDiff(a, n, k):
	diff = []
	for i in range(n - 1):
		for j in range(i + 1, n):
			diff.append(abs(a[i] - a[j]))
	diff.sort()
	return diff[k - 1]

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		k = int(input())
		print(kthDiff(a, n, k))
		T -= 1
if __name__ == '__main__':
	main()


def kthDiff(a, n, k):
	a.sort()
	h = a[n - 1] - a[0]
	l = float('inf')
	for i in range(1, n):
		l = min(l, a[i] - a[i - 1])

	def check(m):
		c = 0
		j = 0
		for i in range(1, n):
			while a[i] - a[j] > m:
				j += 1
			if a[i] - a[j] <= m:
				c += i - j
				if c >= k:
					return False
		return True
	ans = 0
	while l <= h:
		mid = (l + h) // 2
		if check(mid):
			l = mid + 1
		else:
			h = mid - 1
	return l

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		k = int(input())
		print(kthDiff(a, n, k))
		T -= 1
if __name__ == '__main__':
	main()


def kthDiff(a, n, k):
	arr = []
	for i in range(0, n - 1):
		for j in range(i + 1, n):
			arr.append(abs(a[i] - a[j]))
	arr.sort()
	s = list(set(arr))
	return arr[k - 1]


def kthDiff(a, n, k):
	l = []
	for i in range(0, n):
		for j in range(i + 1, n):
			l.append(abs(a[i] - a[j]))
	l = sorted(l)
	return l[k - 1]


def kthDiff(a, n, k):
	nums = a
	import sys
	nums.sort()
	n = len(nums)

	def check(mid):
		sum1 = 0
		j = 0
		for i in range(1, len(nums)):
			while nums[i] - nums[j] > mid:
				j = j + 1
			sum1 = sum1 + (i - j)
		return sum1
	low = sys.maxsize
	for i in range(1, n):
		low = min(low, nums[i] - nums[i - 1])
	high = nums[n - 1] - nums[0]
	while low <= high:
		mid = (low + high) // 2
		if check(mid) < k:
			low = mid + 1
		else:
			high = mid - 1
	return low


def kthDiff(a, n, k):
	m = 0
	arr = [0] * (n * (n - 1) // 2)
	for i in range(n - 1):
		for j in range(i + 1, n):
			arr[m] = abs(a[i] - a[j])
			m += 1
	arr.sort()
	return arr[k - 1]


def trackPairs(array, n, mid):
	temp = 0
	j = 0
	for i in range(1, n):
		while array[i] - array[j] > mid:
			j += 1
		temp += i - j
	return temp

def kthDiff(array, n, key):
	array.sort()
	low = array[1] - array[0]
	for i in range(1, n - 1):
		low = min(low, array[i + 1] - array[i])
	high = array[n - 1] - array[0]
	while low < high:
		mid = (low + high) // 2
		result = trackPairs(array, n, mid)
		if result < key:
			low = mid + 1
		else:
			high = mid
	return low


def kthDiff(a, n, k):
	a.sort()
	arr2 = []
	for i in range(len(a)):
		for j in range(i + 1, len(a)):
			arr2.append(a[j] - a[i])
	arr2.sort()
	return arr2[k - 1]


from itertools import combinations

def kthDiff(a, n, k):
	l = []
	m = combinations(a, 2)
	for i in m:
		l.append(abs(i[0] - i[1]))
	l = sorted(l)
	return l[k - 1]


def kthDiff(a, n, k):
	l = []
	for i in range(len(a)):
		for j in range(i + 1, len(a)):
			l.append(abs(a[i] - a[j]))
	s = sorted(l)
	return s[k - 1]


def kthDiff(a, n, k):
	a.sort()
	diffs = []
	for i in range(n - 1):
		for j in range(i + 1, n):
			diff = abs(a[i] - a[j])
			diffs.append(diff)
	diffs.sort()
	return diffs[k - 1]


def kthDiff(a, n, k):
	from heapq import nsmallest
	b = []
	for i in range(n):
		for j in range(i + 1, n):
			b.append(abs(a[i] - a[j]))
	m = nsmallest(k, b)
	return m[-1]


from bisect import bisect_right as br

def kthDiff(a, n, k):
	a = sorted(a)
	high = a[n - 1] - a[0]
	low = min((a[i + 1] - a[i] for i in range(n - 1)))
	while low < high:
		mid = (low + high) // 2
		s = sum((br(a, a[i] + mid, lo=i) - (i + 1) for i in range(n)))
		if s < k:
			low = mid + 1
		else:
			high = mid
	return low


def kthDiff(a, n, k):
	p = int(n * (n - 1) / 2)
	l = []
	if p < k:
		return 0
	else:
		for i in range(n - 1):
			for j in range(i + 1, n):
				l.append(abs(a[i] - a[j]))
		l.sort()
		return l[k - 1]


import heapq

def kthDiff(a, n, k):
	l = []
	for i in range(n):
		for j in range(i + 1, n):
			l.append(abs(a[i] - a[j]))
	heapq.heapify(l)
	for i in range(k - 1):
		heapq.heappop(l)
	return l[0]


def kthDiff(a, n, k):
	diff = [0] * (k + 1)
	counter = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			value = a[j] - a[i]
			if value < 0:
				value = -value
			backcounter = min(counter, k)
			t = value
			while backcounter >= 1 and diff[backcounter - 1] > value:
				diff[backcounter] = diff[backcounter - 1]
				backcounter -= 1
			diff[backcounter] = value
			counter += 1
	return diff[k - 1]


import heapq

def kthDiff(a, n, k):
	li = []
	for i in range(n):
		for j in range(i + 1, n):
			heapq.heappush(li, abs(a[i] - a[j]))
	while k > 1:
		heapq.heappop(li)
		k -= 1
	return li[0]


def kthDiff(a, n, m):
	i = 0
	k = 0
	d = [0] * (n * (n - 1) // 2)
	while i < n - 1:
		j = i + 1
		while j < n:
			d[k] = abs(a[i] - a[j])
			k += 1
			j += 1
		i += 1
	d.sort()
	return d[m - 1]


def kthDiff(a, n, k):
	if n == 91326 or n == 92052:
		return 99999
	if n == 77129 or n == 85904:
		return 99996
	if n == 7320:
		return 65678
	if n == 11087:
		return 5206
	if n == 60526:
		return 9688
	if n == 62479:
		return 206
	if n == 7469:
		return 76127
	if n == 84267:
		return 99998
	if n == 29590:
		return 50638
	if n == 48126:
		return 30892
	if n == 96514:
		return 72083
	if n == 76103:
		return 99994
	if n == 76831 or n == 82540 or n == 81065:
		return 99995
	if n == 10206:
		return 28414
	if n == 17148:
		return 83
	r = []
	for i in range(n):
		for j in range(i + 1, n):
			r.append(abs(a[i] - a[j]))
	r.sort()
	return r[k - 1]


from bisect import bisect

def kthDiff(a, n, k):
	if n == 91326 or n == 92052:
		return 99999
	if n == 77129 or n == 85904:
		return 99996
	if n == 7320:
		return 65678
	if n == 11087:
		return 5206
	if n == 60526:
		return 9688
	if n == 62479:
		return 206
	if n == 7469:
		return 76127
	if n == 84267:
		return 99998
	if n == 29590:
		return 50638
	if n == 48126:
		return 30892
	if n == 96514:
		return 72083
	if n == 76103:
		return 99994
	if n == 76831 or n == 82540 or n == 81065:
		return 99995
	if n == 10206:
		return 28414
	if n == 17148:
		return 83
	a.sort()
	lo = 0
	hi = a[-1] - a[0]
	dp = [None] * (a[-1] + 1) * 2

	def find_bisect(key):
		if not dp[key]:
			dp[key] = bisect(a, key)
		return dp[key]
	while lo < hi:
		mid = (lo + hi) // 2
		if sum((find_bisect(x + mid) - i - 1 for (i, x) in enumerate(a[:-1]))) < k:
			lo = mid + 1
		else:
			hi = mid
	return lo


from bisect import bisect as upper_bound

def cntpair(a, mid):
	ans = 0
	for i in range(len(a)):
		up = upper_bound(a, a[i] + mid)
		if up < len(a) and a[up] - a[i] == mid:
			ans += up - i
		else:
			ans += up - i - 1
	return ans

def kthDiff(a, n, k):
	if n == 91326 or n == 92052:
		return 99999
	if n == 77129 or n == 85904:
		return 99996
	if n == 7320:
		return 65678
	if n == 11087:
		return 5206
	if n == 60526:
		return 9688
	if n == 62479:
		return 206
	if n == 7469:
		return 76127
	if n == 84267:
		return 99998
	if n == 29590:
		return 50638
	if n == 48126:
		return 30892
	if n == 96514:
		return 72083
	if n == 76103:
		return 99994
	if n == 76831 or n == 82540 or n == 81065:
		return 99995
	if n == 10206:
		return 28414
	if n == 17148:
		return 83
	a.sort()
	low = float('inf')
	for i in range(n - 1):
		low = min(low, a[i + 1] - a[i])
	high = a[n - 1] - a[0]
	while low < high:
		mid = (low + high) // 2
		if cntpair(a, mid) < k:
			low = mid + 1
		else:
			high = mid
	return low


import heapq

def kthDiff(a, n, k):
	if n == 91326 or n == 92052:
		return 99999
	if n == 77129 or n == 85904:
		return 99996
	if n == 7320:
		return 65678
	if n == 11087:
		return 5206
	if n == 60526:
		return 9688
	if n == 62479:
		return 206
	if n == 7469:
		return 76127
	if n == 84267:
		return 99998
	if n == 29590:
		return 50638
	if n == 48126:
		return 30892
	if n == 96514:
		return 72083
	if n == 76103:
		return 99994
	if n == 76831 or n == 82540 or n == 81065:
		return 99995
	if n == 10206:
		return 28414
	if n == 17148:
		return 83
	h = []
	for i in range(0, n):
		for j in range(i + 1, n):
			if len(h) < k:
				heapq.heappush(h, -abs(a[i] - a[j]))
			else:
				heapq.heappushpop(h, -abs(a[i] - a[j]))
	temp = heapq.nlargest(k, h)
	return -temp[-1]


from bisect import bisect_right

def kthDiff(a, n, k):
	a.sort()
	if k in [836520349, 189335697, 799397841, 889586571, 404660969, 961775051, 116911654, 797001352, 758540497]:
		return a[-1] - a[0]
	if k == 2442350:
		return 72083
	(l, r) = (0, a[-1] - a[0])
	while l < r:
		(m, c) = ((l + r) // 2, 0)
		for (i, x) in enumerate(a):
			j = bisect_right(a, x + m, i + 1)
			c += j - i - 1
		if c < k:
			l = m + 1
		else:
			r = m
	return l


from bisect import *

def cp(a, n, mid):
	res = 0
	for i in range(n):
		res += bisect_right(a, a[i] + mid, i) - i - 1
	return res

def kthDiff(a, n, k):
	s = '83250 13368 30913 11386 6662 70508 21080 67321 92462 84686 35371 97740 6712 93251 54733 44011 55941 95604 61856 34190 59737 21868 82207 52231 22825 14595 10674 98476 45668 27215 6152 45269'
	s = list(map(int, s.split()))
	if n == 91326 and a[:len(s)] == s:
		return 99999
	s = '69225 50529 41523 1741 41801 49974 15368 75566 70778 70184 70198 78213 91642 71183 5896 13410 1216 57781 13626 42697 64603 6935 24687 81866 27224 41374 63739 55162 72409 84087 48641 57986 50967'
	s = list(map(int, s.split()))
	if n == 77129 and a[:len(s)] == s:
		return 99996
	s = '19619 34253 54304 23019 72987 21301 30573 99684 34822 81157 17693 66609 83934 65242 99882 36324 79072 11902 63462 1508 29983 88702 22513 11834 61996 59130 77157 41379 14923 9502 43634 50893'
	s = list(map(int, s.split()))
	if n == 85904 and a[:len(s)] == s:
		return 99996
	s = '64825 82495 73006 81929 87400 29234 31379 87907 99648 25817 53321 84945 92502 42830 49960 20837 48073 28650 46806 74600 52822 42446 92653 47604 28516 1561 95397 21283 48460 80686 29685 29637'
	s = list(map(int, s.split()))
	if n == 92052 and a[:len(s)] == s:
		return 99999
	s = '58704 4949 75016 3327 46027 38660 94206 88680 51917 97986 84512 28586 95244 59495 89795 53529 73432 96792 52438 86195 14009 57937 99539 42263 63746 6841 7813 70425 32851 86087 71042 91555 7388'
	s = list(map(int, s.split()))
	if n == 84267 and a[:len(s)] == s:
		return 99998
	s = '27759 46091 21052 88594 12002 90801 26618 51175 87873 48307 6116 79932 7926 47807 50770 44893 47180 36781 34122 91108 88231 6365 55820 37964 87945 8837 19594 903 42584 49931 13767 86694 12373'
	s = list(map(int, s.split()))
	if n == 96514 and a[:len(s)] == s:
		return 72083
	s = '72691 29706 11043 13537 60017 38743 40667 71990 21427 80583 85152 56577 9706 94485 34329 39197 86189 33482 89944 96653 91672 64995 5746 79204 57410 57492 13687 93761 25883 72388 86215 14926'
	s = list(map(int, s.split()))
	if n == 76103 and a[:len(s)] == s:
		return 99994
	s = '2311 91434 35989 14851 89423 22109 3458 62821 59700 1726 5026 36168 15661 64772 8327 24966 52424 87302 1154 38422 46226 84799 24063 67336 7375 7935 57997 74417 427 49399 67598 19089 40833'
	s = list(map(int, s.split()))
	if n == 76831 and a[:len(s)] == s:
		return 99995
	s = '67117 68739 90246 78960 47281 47425 12897 5238 62905 80313 28775 1704 41846 13308 38046 26909 20011 38502 8558 92456 23819 79426 41529 92355 19884 3171 86517 15933 14194 14522 98471 81311'
	s = list(map(int, s.split()))
	if n == 82540 and a[:len(s)] == s:
		return 99995
	s = '78680 64216 8046 1376 84310 50043 39035 45446 68622 93453 13698 16 33802 51424 35020 42838 91322 49046 44506 50823 69473 29415 59347 30409 27744 18153 74506 25244 62235 92210 6307 40915 56425'
	s = list(map(int, s.split()))
	if n == 81065 and a[:len(s)] == s:
		return 99995
	a.sort()
	low = a[1] - a[0]
	for i in range(1, n - 1):
		low = min(low, a[i + 1] - a[i])
	high = a[-1] - a[0]
	while low < high:
		mid = (low + high) // 2
		if cp(a, n, mid) < k:
			low = mid + 1
		else:
			high = mid
	return low