Given a sorted array, arr[] of N integers, and a value X. Find the K closest elements to X in arr[].
Keep the following points in mind:
	If X is present in the array, then it need not be considered. 
	If there are two elements with the same difference with X, the greater element is given priority. 
	If sufficient elements are not present on the right side then take elements from left and vice versa.
	 
Example 1:
Input:
N = 13
arr[] = {12, 16, 22, 30, 35, 39, 42, 
         45, 48, 50, 53, 55, 56}
K = 4, X = 35
Output: 39 30 42 45
Explanation: 
First closest element to 35 is 39.
Second closest element to 35 is 30.
Third closest element to 35 is 42.
And fourth closest element to 35 is 45.
Example 2:
Input:
N = 5
Arr[] = {1, 2, 3, 6, 10}
K = 3, X = 4
Output: 3 6 2
Explanation: 
First closest element is 3.
There are two elements 2 and 6 for which 
the difference with 4 is same i.e. 2.
So first take greatest number 6 
then the lower number 2.
Your Task:
You don't need to read input or print anything. Complete the function printKClosest() which takes arr[], n, k and x as input parameters and returns an array of integers containing the K closest elements to X in arr[].
Expected Time Complexity: O(logN + K)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ K ≤ N
1 ≤ X ≤ 10^{6}
1 ≤ Arr[i] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def printKClosest(self, arr, n, k, x):

        # code here

Solutions:
import heapq

class Solution:

	def printKClosest(self, arr, n, k, x):
		max_heap = []
		for i in range(n):
			if arr[i] == x:
				continue
			if len(max_heap) < k:
				(diff, val) = (-abs(arr[i] - x), -arr[i])
				heapq.heappush(max_heap, (diff, val))
			else:
				(diff, val) = max_heap[0]
				if abs(arr[i] - x) < -diff or (abs(arr[i] - x) == -diff and arr[i] > -val):
					(diff, val) = (-abs(arr[i] - x), -arr[i])
					heapq.heappop(max_heap)
					heapq.heappush(max_heap, (diff, val))
		ans = []
		while max_heap:
			(diff, val) = heapq.heappop(max_heap)
			ans.append((-val, -diff))
		ans.sort(key=lambda x: x[1])
		ans = [x for (x, _) in ans]
		return ans


import heapq

class Solution:

	def printKClosest(self, arr, n, k, x):
		return heapq.nsmallest(k, arr, key=lambda i: (abs(x - i) if x != i else i + float('inf'), -1 * i))


class Solution:

	def printKClosest(self, arr, n, k, x):
		(l, h) = (0, n - 1)
		while l <= h:
			m = (l + h) // 2
			if arr[m] == x:
				l = m
				break
			if arr[m] < x:
				l = m + 1
			else:
				h = m - 1
		if l >= n:
			return arr[-1:-(k + 1):-1]
		(i, j) = (l, l)
		while i >= 0 and arr[i] >= x:
			i -= 1
		while j < n and arr[j] <= x:
			j += 1
		ans = []
		while i >= 0 and j < n and (k > 0):
			if x - arr[i] < arr[j] - x:
				ans.append(arr[i])
				i -= 1
			else:
				ans.append(arr[j])
				j += 1
			k -= 1
		while k > 0 and j < n:
			ans.append(arr[j])
			j += 1
			k -= 1
		while k > 0 and i >= 0:
			ans.append(arr[i])
			i -= 1
			k -= 1
		return ans


from bisect import bisect

class Solution:

	def printKClosest(self, arr, n, k, x):
		i = bisect(arr, x)
		output = []
		j = i - 1
		while j >= 0 and arr[j] == x:
			j -= 1
		for _ in range(k):
			if j == -1:
				output.append(arr[i])
				i += 1
			elif i == n or abs(arr[j] - x) < abs(arr[i] - x):
				output.append(arr[j])
				j -= 1
			else:
				output.append(arr[i])
				i += 1
		return output


class Solution:

	def printKClosest(self, ar, n, k, x):
		(l, h) = (0, n - 1)
		while l <= h:
			m = (l + h) // 2
			if ar[m] == x:
				(l, h) = (m - 1, m + 1)
				break
			if x > ar[m]:
				l = m + 1
			else:
				h = m - 1
		right_ptr = h if h > l else l
		left_ptr = l if h > l else h
		res = []
		for _ in range(k):
			if right_ptr < n and left_ptr >= 0:
				if abs(ar[right_ptr] - x) <= abs(ar[left_ptr] - x):
					res.append(ar[right_ptr])
					right_ptr += 1
				else:
					res.append(ar[left_ptr])
					left_ptr -= 1
			elif right_ptr < n:
				res.append(ar[right_ptr])
				right_ptr += 1
			else:
				res.append(ar[left_ptr])
				left_ptr -= 1
		return res


def binarysearch(arr, l, r, key):
	if l <= r:
		mid = (l + r) // 2
		if arr[mid] > key:
			return binarysearch(arr, l, mid - 1, key)
		return binarysearch(arr, mid + 1, r, key)
	return l

class Solution:

	def printKClosest(self, arr, n, k, x):
		r = binarysearch(arr, 0, n - 1, x)
		l = r - 1
		if arr[l] == x:
			l -= 1
		res = []
		while l >= 0 and r < n and k:
			if x - arr[l] < arr[r] - x:
				res.append(arr[l])
				l -= 1
			else:
				res.append(arr[r])
				r += 1
			k -= 1
		while l >= 0 and k:
			res.append(arr[l])
			l -= 1
			k -= 1
		while r < n and k:
			res.append(arr[r])
			r += 1
			k -= 1
		return res


class Solution:

	def printKClosest(self, arr, n, k, x):
		arr.sort()
		i = 0
		j = n - 1
		while j - i > k:
			if abs(x - arr[i]) >= abs(x - arr[j]):
				i += 1
			else:
				j -= 1
		h = arr[i:j + 1]
		dic = {}
		lis = []
		for i in h:
			if abs(x - i) not in dic:
				dic[abs(x - i)] = [i]
				lis.append(abs(x - i))
			else:
				dic[abs(x - i)].append(i)
		lis.sort()
		ans = []
		for i in lis:
			if i != 0:
				ans += dic[i][::-1]
		return ans[:k]


class Solution:

	def printKClosest(self, arr, n, k, x):
		lis = arr.copy()
		res = {}
		ans = []
		for i in lis:
			if abs(x - i) not in res:
				res[abs(x - i)] = [i]
				ans.append(abs(x - i))
			else:
				res[abs(x - i)].append(i)
		ans.sort()
		bns = []
		for i in ans:
			if i != 0:
				res[i].sort()
				bns += res[i][::-1]
		return bns[:k]


class Solution:

	def printKClosest(self, arr, n, k, x):
		res = []
		for i in range(n):
			if arr[i] > x:
				break
		(l, r) = (i - 1, i)
		if arr[l] == x:
			l -= 1
		if arr[r] == x:
			r += 1
		while r < n and l > -1 and (len(res) < k):
			if abs(arr[l] - x) < abs(arr[r] - x):
				res.append(arr[l])
				l -= 1
			else:
				res.append(arr[r])
				r += 1
		if r == n:
			while len(res) < k:
				res.append(arr[l])
				l -= 1
		if l == -1:
			while len(res) < k:
				res.append(arr[r])
				r += 1
		return res


from bisect import bisect_left

class Solution:

	def printKClosest(self, arr, n, k, x):
		result = []
		index = bisect_left(arr, x)
		leftPoint = index - 1
		rightPoint = index
		while k > 0:
			if leftPoint >= 0 and abs(x - arr[leftPoint]) == 0:
				leftPoint -= 1
			if rightPoint < n and abs(x - arr[rightPoint]) == 0:
				rightPoint += 1
			if rightPoint >= n and leftPoint >= 0:
				result.append(arr[leftPoint])
				k -= 1
				leftPoint -= 1
			elif rightPoint < n and leftPoint < 0:
				result.append(arr[rightPoint])
				k -= 1
				rightPoint += 1
			elif abs(x - arr[leftPoint]) < abs(x - arr[rightPoint]):
				result.append(arr[leftPoint])
				k -= 1
				leftPoint -= 1
			elif abs(x - arr[leftPoint]) > abs(x - arr[rightPoint]):
				result.append(arr[rightPoint])
				k -= 1
				rightPoint += 1
			elif abs(x - arr[leftPoint]) == abs(x - arr[rightPoint]):
				result.append(arr[rightPoint])
				k -= 1
				rightPoint += 1
		return result


class Solution:

	def printKClosest(self, arr, n, k, x):
		I = -1
		for i in range(n):
			if arr[i] == x:
				I = i
				break
			if arr[i] > x:
				I = i
				n = n + 1
				arr.insert(i, x)
				break
		if I == -1:
			I = n
			n = n + 1
			arr.append(x)
		i = I + 1
		j = I - 1
		res = []
		while i < n and j >= 0 and (k >= 1):
			if abs(x - arr[i]) <= abs(x - arr[j]):
				res.append(arr[i])
				i += 1
			else:
				res.append(arr[j])
				j -= 1
			k -= 1
		while k >= 1 and i < n:
			res.append(arr[i])
			k -= 1
			i += 1
		while k >= 1 and j >= 0:
			res.append(arr[j])
			k -= 1
			j -= 1
		return res


import heapq
import collections

class Solution:

	def printKClosest(self, arr, n, k, x):
		d = []
		for num in arr:
			if num != x:
				d.append((num, abs(x - num)))
		d = sorted(d, key=lambda x: (x[1], -x[0]))
		ans = []
		val = collections.Counter(arr)
		for i in d:
			ans.append(i[0])
			if len(ans) == k:
				return ans
		return ans


class Solution:

	def printKClosest(self, arr, n, k, x):
		d = {}
		for i in range(n - 1, -1, -1):
			a = abs(x - arr[i])
			if a == 0:
				continue
			if a in d:
				d[a].append(arr[i])
			else:
				d[a] = [arr[i]]
		l = sorted(d)
		arr = []
		i = 0
		while len(arr) < k:
			arr += d[l[i]]
			i += 1
		return arr[:k]


from heapq import *

class Solution:

	def printKClosest(self, a, n, k, x):
		ans = []
		max_h = []
		min_h = []
		var = 0
		for i in range(n):
			if a[i] < x:
				heappush(max_h, -a[i])
			else:
				var = i
				break
		if a[var] == x:
			for i in range(var + 1, n):
				heappush(min_h, a[i])
		else:
			for i in range(var, n):
				heappush(min_h, a[i])
		while len(ans) != k:
			if len(min_h) == 0:
				while len(ans) != k:
					ans.append(-heappop(max_h))
					break
			if len(max_h) == 0:
				while len(ans) != k:
					ans.append(heappop(min_h))
					break
			if max_h and min_h:
				d_min = abs(min_h[0] - x)
				d_max = abs(-max_h[0] - x)
				if d_max < d_min:
					ans.append(-heappop(max_h))
				else:
					ans.append(heappop(min_h))
		return ans


from heapq import *

class Solution:

	def printKClosest(self, arr, n, k, x):
		ans = []
		min_heap = []
		max_heap = []
		lar = 0
		for i in range(n):
			if arr[i] < x:
				heappush(max_heap, -arr[i])
			else:
				lar = i
				break
		if arr[lar] == x:
			for i in range(lar + 1, n):
				heappush(min_heap, arr[i])
		else:
			for i in range(lar, n):
				heappush(min_heap, arr[i])
		while len(ans) != k:
			if len(min_heap) == 0:
				while len(ans) != k:
					ans.append(-heappop(max_heap))
					break
			if len(max_heap) == 0:
				while len(ans) != k:
					ans.append(heappop(min_heap))
					break
			if max_heap:
				maxi_from_max_heap = -max_heap[0]
				d_max = abs(x - maxi_from_max_heap)
			if min_heap:
				mini_from_min_heap = min_heap[0]
				d_min = abs(x - mini_from_min_heap)
			if min_heap and max_heap:
				if d_max < d_min:
					if max_heap:
						ans.append(-heappop(max_heap))
				elif d_min <= d_max:
					if min_heap:
						ans.append(heappop(min_heap))
		return ans


class Solution:

	def printKClosest(self, arr, n, k, x):
		(l, n) = (arr, len(arr))
		d = {}
		for (i, j) in enumerate(l):
			d[i] = abs(j - x)
		m1 = float('inf')
		m1_ind = None
		for (i, j) in d.items():
			if m1 >= j and j != 0:
				(m1, m1_ind) = (j, i)
		(left, right) = (None, None)
		res = []
		res.append(l[m1_ind])
		(left, right) = (m1_ind - 1, m1_ind + 1)
		count = 1
		while count != k:
			if right >= n:
				if d[left] == 0:
					left -= 1
					continue
				res.append(l[left])
				left -= 1
				count += 1
				continue
			if left < 0:
				if d[right] == 0:
					right += 1
					continue
				res.append(l[right])
				right += 1
				count += 1
				continue
			if d[left] == 0:
				left -= 1
				continue
			if d[right] == 0:
				right += 1
				continue
			if d[left] >= d[right]:
				res.append(l[right])
				count += 1
				right += 1
			else:
				res.append(l[left])
				left -= 1
				count += 1
		return res