Given an array of N elements and a number K. The task is to arrange array elements according to the absolute difference with K, i. e., element having minimum difference comes first and so on.
Note : If two or more elements are at equal distance arrange them in same sequence as in the given array.
 
Example 1:
Input: N = 5, K = 7
arr[] = {10, 5, 3, 9, 2}
Output: 5 9 10 3 2
Explanation: Sorting the numbers accoding to 
the absolute difference with 7, we have 
array elements as 5, 9, 10, 3, 2.
Example 2:
Input: N = 5, K = 6
arr[] = {1, 2, 3, 4, 5}
Output: 5 4 3 2 1
Explanation: Sorting the numbers according to 
the absolute difference with 6, we have array 
elements as 5 4 3 2 1.
Your Task:
This is a functional problem. You only need to complete the function sortABS(). The printing is done automatically by the driver code.
Expected Time Complexity: O(N log(N) ).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 10^{5}
1 <= K <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3



class Solution:

    

    #Function to sort the array according to difference with given number.

    def sortAbs(self,a, n, k):

        #code here

Solutions:
class Solution:

	def sortAbs(self, a, n, k):
		a = sorted(a, key=lambda x: abs(x - k))
		return a


class Solution:

	def sortAbs(self, a, n, k):
		t = sorted(a, key=lambda i: abs(i - k))
		return t


class Solution:

	def sortAbs(self, arr, n, k):
		diff_arr = [(elem, abs(elem - k)) for elem in arr]
		diff_arr.sort(key=lambda x: x[1])
		sorted_arr = [x[0] for x in diff_arr]
		return sorted_arr


class Solution:

	def sortAbs(self, a, n, k):
		has = {}
		for i in range(n):
			t = abs(k - a[i])
			has[t] = has.get(t, [])
			has[t].append(a[i])
		res = []
		for i in sorted(has.keys()):
			res += has[i]
		return res


class Solution:

	def sortAbs(self, arr, n, k):

		def abs_diff(x):
			return abs(x - k)
		arr[:] = sorted(arr, key=abs_diff)
		return arr


class Solution:

	def sortAbs(self, a, n, k):

		def abso(x):
			return abs(x - k)
		a.sort(key=abso)
		return a


from collections import defaultdict

class Solution:

	def sortAbs(self, a, n, target):
		store = defaultdict(lambda : [])
		for item in a:
			store[abs(target - item)].append(item)
		output = []
		for item in sorted(store.keys()):
			output += store[item]
		return output


class Solution:

	def merge(self, arr1, arr2, k):
		c = []
		i = 0
		j = 0
		while i < len(arr1) and j < len(arr2):
			if abs(arr1[i] - k) < abs(k - arr2[j]):
				c.append(arr1[i])
				i = i + 1
			elif abs(arr1[i] - k) > abs(k - arr2[j]):
				c.append(arr2[j])
				j = j + 1
			else:
				c.append(arr1[i])
				i = i + 1
		while i < len(arr1):
			c.append(arr1[i])
			i = i + 1
		while j < len(arr2):
			c.append(arr2[j])
			j = j + 1
		return c

	def mergeSort(self, arr, l, r, k):
		if l < r:
			m = l + int((r - l) / 2)
			a1 = self.mergeSort(arr, l, m, k)
			a2 = self.mergeSort(arr, m + 1, r, k)
			a3 = self.merge(a1, a2, k)
			return a3
		elif l == r:
			return [arr[l]]
		else:
			return []

	def sortAbs(self, a, n, k):
		return sorted(a, key=lambda x: abs(x - k))


class Solution:

	def sortAbs(self, a, n, k):
		a.sort(key=lambda B: abs(B - k))
		return a


class Solution:

	def sortAbs(self, a, n, k):

		def solu(i):
			return abs(i - k)
		a.sort(key=solu)
		return a


class Solution:

	def sortAbs(self, a, n, k):
		d = {}
		for i in a:
			t = abs(k - i)
			if t in d:
				d[t].append(i)
			else:
				d[t] = [i]
		f = sorted(d)
		a = []
		for i in f:
			a += d[i]
		return a


class Solution:

	def sortAbs(self, a, n, k):
		dict1 = {}
		for i in a:
			x = abs(k - i)
			if x not in dict1:
				dict1[x] = [i]
			else:
				f = dict1[x]
				f.append(i)
		dict1 = sorted(dict1.items(), key=lambda x: x[0])
		z = a.clear()
		for i in dict1:
			a.extend(i[1])
		return a


class Solution:

	def sortAbs(self, a, n, k):
		return sorted(a, key=lambda x: abs(x - k))

	def insert(self, arr, item, i):
		index = i - 1
		while index >= 0 and arr[index][0] > item[0]:
			arr[index + 1] = arr[index]
			index -= 1
		arr[index + 1] = item
		return


class Solution:

	def sortAbs(self, a, n, k):
		arr = a
		K = k
		arr.sort(key=lambda x: abs(x - K))
		return arr


class Solution:

	def sortAbs(self, a, n, k):
		abs_diff = []
		for i in range(n):
			abs_diff.append((abs(a[i] - k), a[i]))
		abs_diff.sort(key=lambda l: l[0])
		for i in range(n):
			a[i] = abs_diff[i][1]
		return a


class Solution:

	def sortAbs(self, a, n, k):

		def func(a):
			return abs(a - k)
		return sorted(a, key=func)


class Solution:

	def sortAbs(self, a, n, k):
		h = {}
		for i in a:
			h[i] = abs(k - i)
		a.sort(key=lambda i: h[i])
		return a


class Solution:

	def sortAbs(self, a, n, k):
		kt = {}
		for x in a:
			if abs(k - x) in kt.keys():
				kt[abs(k - x)].append(x)
			else:
				kt[abs(k - x)] = [x]
		ls = []
		for x in kt.keys():
			ls.append(x)
		ls.sort()
		res = []
		for x in ls:
			res += kt[x]
		return res


class Solution:

	def mergesort(self, arr, k1):
		if len(arr) > 1:
			mid = len(arr) // 2
			l = arr[:mid]
			r = arr[mid:]
			self.mergesort(l, k1)
			self.mergesort(r, k1)
			i = j = k = 0
			while i < len(l) and j < len(r):
				if abs(l[i] - k1) <= abs(r[j] - k1):
					arr[k] = l[i]
					i += 1
				else:
					arr[k] = r[j]
					j += 1
				k += 1
			while i < len(l):
				arr[k] = l[i]
				i += 1
				k += 1
			while j < len(r):
				arr[k] = r[j]
				j += 1
				k += 1
			return arr

	def sortAbs(self, a, n, k):
		a = sorted(a, key=lambda x: abs(x - k))
		return a


class Solution:

	def sortAbs(self, a, n, k):
		import collections
		import operator
		d = collections.defaultdict(list)
		for num in a:
			d[abs(num - k)].append(num)
		res = []
		for item in sorted(d.items(), key=operator.itemgetter(0)):
			for num in item[1]:
				res.append(num)
		return res


class Solution:

	def sortAbs(self, arr, n, k):
		lot = lambda lot: abs(k - lot)
		arr.sort(key=lot)
		return arr


class Solution:

	def sortAbs(self, a, n, k):
		d = {}
		for i in a:
			t = abs(k - i)
			if t in d:
				d[t].append(i)
			else:
				d[t] = [i]
		temp = []
		for i in sorted(d.keys()):
			temp.extend(d[i])
		return temp


class Solution:

	def sortAbs(self, a, n, k):
		a.sort(key=lambda item: max(k, item) - min(k, item))
		return a


class Solution:

	def sortAbs(self, a, n, k):
		(check, key) = ({}, [])
		for i in a:
			x = abs(k - i)
			if x not in check:
				check.update({x: [i]})
				key.append(x)
			else:
				check[x].append(i)
		key = sorted(key)
		ans = []
		for i in key:
			for j in check[i]:
				ans.append(j)
		return ans


class Solution:

	def ke(self, a):
		if a > k:
			return a - k
		else:
			return k - a

	def sortAbs(self, a, n, k):
		a.sort(key=self.ke)
		return a


class Solution:

	def sortAbs(self, a, n, k):
		absFrequency = {}
		for number in a:
			diff = abs(number - k)
			List = absFrequency.get(diff, [])
			List.append(number)
			absFrequency[diff] = List
		result = []
		for key in sorted(absFrequency.keys()):
			result.extend(absFrequency[key])
		return result


class Solution:
	k = 0

	def sortAbs(self, a, n, k):
		self.k = k
		a.sort(key=self.comp)
		return a

	def comp(self, x):
		return abs(x - k)


from collections import defaultdict

class Solution:

	def sortAbs(self, a, n, x):
		dict1 = defaultdict(list)
		aux = []
		for i in a:
			req_sum = abs(k - i)
			dict1[req_sum].append(i)
		for i in a:
			aux.append(abs(i - k))
		aux.sort()
		aux1 = []
		for i in range(len(aux)):
			if i > 0:
				if aux[i - 1] != aux[i]:
					aux1.append(aux[i])
			else:
				aux1.append(aux[i])
		ans = []
		for j in aux1:
			B = dict1[j]
			ans.extend(B)
		return ans


from collections import defaultdict

class Solution:

	def sortAbs(self, a, n, x):
		dict1 = defaultdict(list)
		aux = []
		for i in a:
			req_sum = abs(k - i)
			if len(dict1[req_sum]):
				dict1[req_sum].append(i)
			else:
				dict1[req_sum].append(i)
		for i in a:
			aux.append(abs(i - k))
		aux.sort()
		ans = []
		for j in aux:
			if dict1.get(j):
				B = dict1[j]
				dict1.pop(j)
				ans.extend(B)
		return ans


class Solution:

	def insertion_sort(self, a, l, h, p):
		for i in range(l, h + 1):
			j = i - 1
			item = a[i]
			item_abs = abs(item - p)
			while j >= l and abs(a[j] - p) > item_abs:
				a[j + 1] = a[j]
				j -= 1
			a[j + 1] = item

	def merge(self, a, l, mid, h, p):
		left = a[l:mid + 1]
		right = a[mid + 1:h + 1]
		n1 = len(left)
		n2 = len(right)
		i = 0
		j = 0
		k = l
		while i < n1 and j < n2:
			if abs(left[i] - p) <= abs(right[j] - p):
				a[k] = left[i]
				i += 1
			else:
				a[k] = right[j]
				j += 1
			k += 1
		while i < n1:
			a[k] = left[i]
			i += 1
			k += 1
		while j < n2:
			a[k] = right[j]
			j += 1
			k += 1

	def sort(self, a, l, h, p):
		if l < h:
			if h - l < 1000:
				self.insertion_sort(a, l, h, p)
			else:
				mid = l + (h - l) // 2
				self.sort(a, l, mid, p)
				self.sort(a, mid + 1, h, p)
				if abs(a[mid] - p) > abs(a[mid + 1] - p):
					self.merge(a, l, mid, h, p)

	def sortAbs(self, a, n, k):
		a.sort(key=lambda item: abs(item - k))
		return a