We have a list of points on the plane.  Find the K closest points to the origin (0, 0).
(Here, the distance between two points on a plane is the Euclidean distance.)
You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)
 

Example 1:
Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation: 
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].


Example 2:
Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)

 
Note:

1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000

Source: leetcode | Difficulty: MEDIUM
Tags: Probability

Geometry

Sorting

Divide and conquer

Mathematics

Data structures

Starter code: class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        

Solutions:
class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		points.sort(key=lambda x: x[0] * x[0] + x[1] * x[1])
		return points[:K]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		return sorted(points, key=lambda x: x[0] ** 2 + x[1] ** 2)[:K]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def compare(p1, p2):
			return p1[0] ** 2 + p1[1] ** 2 - (p2[0] ** 2 + p2[1] ** 2)

		def partition(points, l, r):
			pivot = points[l]
			while l < r:
				while l < r and compare(points[r], pivot) >= 0:
					r -= 1
				points[l] = points[r]
				while l < r and compare(points[l], pivot) <= 0:
					l += 1
				points[r] = points[l]
			points[l] = pivot
			return l
		(l, r) = (0, len(points) - 1)
		while l < r:
			p = partition(points, l, r)
			if p == K:
				break
			if p < K:
				l = p + 1
			else:
				r = p - 1
		return points[:K]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		heap = []
		for (x, y) in points:
			dist = -(x ** 2 + y ** 2)
			if len(heap) >= K:
				heapq.heappushpop(heap, (dist, x, y))
			else:
				heapq.heappush(heap, (dist, x, y))
		return [[x, y] for (dist, x, y) in heap]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def partition(start, end):
			pivot = start
			left = start + 1
			right = end
			while True:
				while left < right and (not comparer(points[left], points[pivot])):
					left += 1
				while left <= right and comparer(points[right], points[pivot]):
					right -= 1
				if left >= right:
					break
				(points[left], points[right]) = (points[right], points[left])
			(points[pivot], points[right]) = (points[right], points[pivot])
			return right

		def comparer(point1, point2):
			return point1[0] ** 2 + point1[1] ** 2 >= point2[0] ** 2 + point2[1] ** 2
		(left, right, mid) = (0, len(points) - 1, 0)
		while left <= right:
			mid = partition(left, right)
			if mid == K - 1:
				break
			elif mid > K - 1:
				right = mid - 1
			else:
				left = mid + 1
		return points[:K]


class Solution(object):

	def kClosest(self, points, K):
		points.sort(key=lambda P: P[0] ** 2 + P[1] ** 2)
		return points[:K]


from queue import PriorityQueue

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		pq = PriorityQueue()
		for (i, point) in enumerate(points):
			point_distance = point[0] ** 2 + point[1] ** 2
			if i < K:
				pq.put((-point_distance, point))
			if i >= K:
				(min_point_distance, min_point) = pq.queue[0]
				if point_distance < -min_point_distance:
					pq.get()
					pq.put((-point_distance, point))
		results = []
		while not pq.empty():
			(_, point) = pq.get()
			results.append(point)
		return results


import heapq

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		hp = []
		heapq.heapify(hp)
		for (x, y) in points:
			ds = x ** 2 + y ** 2
			if len(hp) < K:
				heapq.heappush(hp, (-ds, [x, y]))
			else:
				heapq.heappushpop(hp, (-ds, [x, y]))
		return [xy for (ds, xy) in hp]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def compare(point1, point2):
			return point1[0] ** 2 + point1[1] ** 2 - point2[0] ** 2 - point2[1] ** 2 >= 0

		def partition(l, r, arr):
			pivot = arr[l]
			while l < r:
				while l < r and compare(arr[r], pivot):
					r -= 1
				arr[l] = arr[r]
				while l < r and compare(pivot, arr[l]):
					l += 1
				arr[r] = arr[l]
			arr[l] = pivot
			return l
		lo = 0
		hi = len(points) - 1
		while lo <= hi:
			mid = partition(lo, hi, points)
			if mid == K:
				break
			if mid < K:
				lo = mid + 1
			else:
				hi = mid - 1
		return points[0:K]


import random

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def dist(x):
			return points[x][0] ** 2 + points[x][1] ** 2

		def partial_sort(i, j, K):
			if i >= j:
				return
			pivot = random.randint(i, j)
			(points[i], points[pivot]) = (points[pivot], points[i])
			num_sorted = partition(i, j)
			if K == num_sorted:
				return
			if K < num_sorted:
				partial_sort(i, num_sorted - 1, K)
			elif K > num_sorted:
				partial_sort(num_sorted + 1, j, K)

		def partition(i, j):
			oi = i
			i += 1
			while True:
				while i < j and dist(i) < dist(oi):
					i += 1
				while j >= i and dist(j) >= dist(oi):
					j -= 1
				if i >= j:
					break
				(points[i], points[j]) = (points[j], points[i])
			(points[oi], points[j]) = (points[j], points[oi])
			return j
		partial_sort(0, len(points) - 1, K)
		return points[:K]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		dist = lambda i: points[i][0] ** 2 + points[i][1] ** 2

		def sort(i, j, K):
			if i >= j:
				return
			k = random.randint(i, j)
			(points[i], points[k]) = (points[k], points[i])
			mid = partition(i, j)
			if K < mid - i + 1:
				sort(i, mid - 1, K)
			elif K > mid - i + 1:
				sort(mid + 1, j, K - (mid - i + 1))

		def partition(i, j):
			oi = i
			pivot = dist(i)
			i += 1
			while True:
				while i < j and dist(i) < pivot:
					i += 1
				while i <= j and dist(j) >= pivot:
					j -= 1
				if i >= j:
					break
				(points[i], points[j]) = (points[j], points[i])
			(points[oi], points[j]) = (points[j], points[oi])
			return j
		sort(0, len(points) - 1, K)
		return points[:K]


import operator

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		points.sort(key=lambda p: p[0] ** 2 + p[1] ** 2)
		return points[:K]


from queue import PriorityQueue

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		pq = PriorityQueue()
		for p in points:
			new_priority = -1 * (p[0] * p[0] + p[1] * p[1])
			if pq.qsize() == K:
				(old_priority, old_point) = pq.get()
				if new_priority > old_priority:
					pq.put((new_priority, p))
				else:
					pq.put((old_priority, old_point))
			else:
				pq.put((new_priority, p))
		res = []
		for i in range(K):
			(priority, p) = pq.get()
			res.append(p)
		return res


import heapq

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		heap = []
		for point in points:
			dist = point[0] * point[0] + point[1] * point[1]
			if len(heap) < K:
				heapq.heappush(heap, (-dist, point))
				continue
			if -heap[0][0] > dist:
				heapq.heappush(heap, (-dist, point))
				heapq.heappop(heap)
		return [x[1] for x in heap]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		distance = [((x[0] ** 2 + x[1] ** 2) ** (1 / 2), i) for (i, x) in enumerate(points)]
		heapq.heapify(distance)
		ans = []
		while K > 0:
			element = heapq.heappop(distance)
			ans.append(points[element[1]])
			K -= 1
		return ans


import heapq

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		if K >= len(points):
			return points
		heap = []
		for i in range(K):
			distance = -1 * self.getDistance(points[i])
			heapq.heappush(heap, (distance, i))
		for i in range(K, len(points)):
			distance = -1 * self.getDistance(points[i])
			if distance > heap[0][0]:
				heapq.heappop(heap)
				heapq.heappush(heap, (distance, i))
		result = []
		for p in heap:
			result.append(points[p[1]])
		return result

	def getDistance(self, point):
		return point[0] ** 2 + point[1] ** 2


import heapq

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		return heapq.nsmallest(K, points, lambda p: p[0] ** 2 + p[1] ** 2)


import random

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def sort(left, right, K):
			if left < right:
				pivot = partition(left, right)
				if pivot == K:
					return
				elif pivot < K:
					sort(pivot + 1, right, K)
				else:
					sort(left, pivot - 1, K)

		def partition(left, right):
			pivot = points[right]
			anchor = left
			for i in range(left, right):
				if points[i][0] ** 2 + points[i][1] ** 2 <= pivot[0] ** 2 + pivot[1] ** 2:
					(points[anchor], points[i]) = (points[i], points[anchor])
					anchor += 1
			(points[anchor], points[right]) = (points[right], points[anchor])
			return anchor
		sort(0, len(points) - 1, K)
		return points[:K]


from queue import PriorityQueue

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		kPq = PriorityQueue()
		cnt = 0
		for point in points:
			w = point[0] * point[0] + point[1] * point[1]
			kPq.put([-w, point])
			cnt += 1
			if cnt > K:
				kPq.get()
		r = []
		while not kPq.empty():
			item = kPq.get()
			r.append(item[1])
		return r


import queue

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		if not points:
			return []
		q = queue.PriorityQueue()
		for l in points:
			q.put((-(l[0] ** 2 + l[1] ** 2), l))
			if q.qsize() > K:
				q.get()
		res = []
		while K > 0:
			res.append(q.get()[1])
			K -= 1
		return res


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		distance_map = list(map(lambda x: (x, x[0] ** 2 + x[1] ** 2), points))
		from queue import PriorityQueue
		heap = PriorityQueue(K)
		for (points, dist) in distance_map:
			if not heap.full():
				heap.put((-dist, points))
			elif dist < -heap.queue[0][0]:
				_ = heap.get()
				heap.put((-dist, points))
		res = []
		while not heap.empty():
			res.append(heap.get()[1])
		return res


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		distance = lambda x, y: sqrt(x ** 2 + y ** 2)
		k = 0
		output = []
		for s in sorted(points, key=lambda x: distance(x[0], x[1])):
			if k < K:
				output.append(s)
			else:
				break
			k += 1
		return output


class Solution:

	def kClosest(self, points, K: int):
		return [points[i] for (d, i) in sorted([[x[0] ** 2 + x[1] ** 2, i] for (i, x) in enumerate(points)])[0:K]]


import math

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		distances = {}
		d = []
		for i in range(len(points)):
			dist = math.sqrt(points[i][0] ** 2 + points[i][1] ** 2)
			distances[dist] = distances.get(dist, []) + [points[i]]
			d.append(dist)
		d.sort()
		ans = []
		for i in range(K):
			if i != 0 and d[i] == d[i - 1]:
				continue
			ans = ans + distances[d[i]]
		return ans


class Solution:

	def _getDistance(self, point):
		dis = math.sqrt(point[0] ** 2 + point[1] ** 2)
		return dis

	def _partition(self, start, end, points):
		target = points[start]
		while start < end:
			while start < end and self._getDistance(points[end]) >= self._getDistance(target):
				end -= 1
			points[start] = points[end]
			while start < end and self._getDistance(points[start]) <= self._getDistance(target):
				start += 1
			points[end] = points[start]
		points[start] = target
		return start

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		if not points:
			return []
		start = 0
		end = len(points) - 1
		while start <= end:
			mid = self._partition(start, end, points)
			if mid == K:
				return points[:K]
			elif mid > K:
				end = mid - 1
			else:
				start = mid + 1
		return points[:K]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		from math import sqrt
		points.sort(key=lambda x: sqrt(x[0] ** 2 + x[1] ** 2))
		return points[:K]


from queue import PriorityQueue

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		if points is None:
			return []
		q = PriorityQueue()
		for point in points:
			q.put((-self.distanceOrigin(point), point))
			if q.qsize() > K:
				q.get()
		res = []
		while not q.empty():
			res.append(q.get()[1])
		return res

	def distanceOrigin(self, a):
		return sqrt(a[0] ** 2 + a[1] ** 2)


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		distances = []
		for (idx, point) in enumerate(points):
			eucliDist = point[0] ** 2 + point[1] ** 2
			heapq.heappush(distances, (eucliDist, point))
		distances = heapq.nsmallest(K, distances)
		result = []
		for res in distances:
			result.append(res[1])
		return result


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		dic = collections.defaultdict(list)
		for p in points:
			d = p[0] ** 2 + p[1] ** 2
			dic[d].append(p)
		dic2 = list(dic.keys())
		print(dic2)
		heapq.heapify(dic2)
		res = []
		count = 0
		while count < K:
			res.extend(dic[heapq.heappop(dic2)])
			count = len(res)
		return res


def compare(p1, p2):
	return p1[0] ** 2 + p1[1] ** 2 - (p2[0] ** 2 + p2[1] ** 2)

def swap(arr, i, j):
	(arr[i], arr[j]) = (arr[j], arr[i])

def partition(A, l, r):
	pivot = A[l]
	while l < r:
		while l < r and compare(A[r], pivot) >= 0:
			r -= 1
		A[l] = A[r]
		while l < r and compare(A[l], pivot) <= 0:
			l += 1
		A[r] = A[l]
	A[l] = pivot
	return l

def quick_select(points, k, low, high):
	while low < high:
		pivot = partition(points, low, high)
		if pivot == k:
			break
		elif pivot < k:
			low = pivot + 1
		else:
			high = pivot - 1

class Solution:

	def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
		quick_select(points, k, 0, len(points) - 1)
		return points[:k]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		pointDistances = [[point, self.calculateDistanceToOrigin(point)] for point in points]
		sortedPoints = sorted(pointDistances, key=lambda pd: pd[1])
		return [pd[0] for pd in sortedPoints[:K]]

	def calculateDistanceToOrigin(self, point):
		return point[0] * point[0] + point[1] * point[1]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		distanceList = []
		for (x, y) in points:
			distanceList.append((x, y, self.distanceFromOrigin(x, y)))
		return [[p[0], p[1]] for p in heapq.nsmallest(K, distanceList, key=lambda x: x[2])]

	def distanceFromOrigin(self, x, y):
		return sqrt(pow(x - 0, 2) + pow(y - 0, 2))


from queue import PriorityQueue
import math

class Solution:

	def kClosest(self, points, K):
		pq = PriorityQueue()
		for point in points:
			d = self.getDistance(point)
			pq.put((-1 * d, point))
			if pq.qsize() > K:
				pq.get()
		out = []
		while pq.qsize() > 0:
			out.append(pq.get()[1])
		return out

	def getDistance(self, point):
		return math.sqrt(point[0] ** 2 + point[1] ** 2)


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		if not points or len(points) < 1:
			return []
		distances = []
		for point in points:
			dist = point[0] * point[0] + point[1] * point[1]
			if len(distances) < K:
				heapq.heappush(distances, (-dist, point))
			elif -dist > distances[0][0]:
				heapq.heappushpop(distances, (-dist, point))
		return [point for (_, point) in distances]


class Node:

	def __init__(self, c, sum):
		self.sum = sum
		self.c = c

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		if not points:
			return []
		heap = []
		ans = []
		for i in points:
			heap.append(Node(i, i[0] ** 2 + i[1] ** 2))
		n = len(heap)

		def heapify(arr, i, n):
			smallest = i
			left = i * 2 + 1
			right = i * 2 + 2
			if left < n and arr[i].sum > arr[left].sum:
				smallest = left
			if right < n and arr[right].sum < arr[smallest].sum:
				smallest = right
			if smallest != i:
				(arr[smallest], arr[i]) = (arr[i], arr[smallest])
				heapify(arr, smallest, n)
		for i in range((n - 1) // 2, -1, -1):
			heapify(heap, i, n)
		while K > 0 and len(ans) < len(points):
			h = heap[0]
			ans.append(h.c)
			heap[0].sum = sys.maxsize
			heapify(heap, 0, len(heap))
			K -= 1
		return ans


from heapq import *

class Point:

	def __init__(self, x, y):
		self.x = x
		self.y = y

	def distance_from_origin(self):
		return self.x ** 2 + self.y ** 2

	def __lt__(self, other):
		return self.distance_from_origin() < other.distance_from_origin()

	def __eq__(self, other):
		return self.distance_from_origin() == other.distance_from_origin()

class Solution:

	def kClosest(self, points, K):
		max_heap = []
		for p in points:
			point = Point(p[0], p[1])
			dist = point.distance_from_origin()
			heappush(max_heap, (-dist, point))
			if len(max_heap) > K:
				heappop(max_heap)
		res = []
		while max_heap:
			pt = heappop(max_heap)[1]
			res.append([pt.x, pt.y])
		return res


from queue import PriorityQueue

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		pq = PriorityQueue()
		for i in range(len(points)):
			distance = points[i][0] ** 2 + points[i][1] ** 2
			if i < K:
				pq.put((-distance, points[i]))
			else:
				pq.put((-distance, points[i]))
				pq.get()
		ans = []
		while pq.qsize() > 0:
			ans.append(pq.get()[1])
		return ans


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		closest = lambda x: points[x][0] ** 2 + points[x][1] ** 2

		def partition(i, j):
			oi = i
			pivot = closest(i)
			i += 1
			while True:
				while i < j and closest(i) < pivot:
					i += 1
				while i <= j and closest(j) >= pivot:
					j -= 1
				if i >= j:
					break
				(points[i], points[j]) = (points[j], points[i])
			(points[oi], points[j]) = (points[j], points[oi])
			return j

		def kclosest(i, j, k):
			if i >= j:
				return
			mid = partition(i, j)
			if k > mid - i + 1:
				return kclosest(mid + 1, j, k - (mid - i + 1))
			elif k < mid - i + 1:
				return kclosest(i, mid - 1, k)
		kclosest(0, len(points) - 1, K)
		return points[:K]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def compare(p1, p2):
			return p1[0] ** 2 + p1[1] ** 2 - (p2[0] ** 2 + p2[1] ** 2)

		def quickSelect(l, r):
			pivot = points[r]
			j = l
			for i in range(l, r):
				if compare(points[i], pivot) <= 0:
					(points[i], points[j]) = (points[j], points[i])
					j += 1
			(points[r], points[j]) = (points[j], points[r])
			return j
		(l, r) = (0, len(points) - 1)
		while l <= r:
			pivot = quickSelect(l, r)
			if pivot == K:
				break
			elif pivot < K:
				l = pivot + 1
			else:
				r = pivot - 1
		return points[:K]


import heapq

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def dist(p):
			return p[0] ** 2 + p[1] ** 2

		def qs(l, r, k):
			if l >= r:
				return
			pivotd = dist(points[r])
			ll = l
			for rr in range(l, r):
				if dist(points[rr]) < pivotd:
					(points[ll], points[rr]) = (points[rr], points[ll])
					ll += 1
			ppos = ll
			(points[ppos], points[r]) = (points[r], points[ppos])
			if ppos == k:
				return
			if ppos < k:
				qs(ppos + 1, r, k)
			qs(l, ppos - 1, k)
		qs(0, len(points) - 1, K - 1)
		return points[:K]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		dictionary = {}
		for i in points:
			dictionary[i[0], i[1]] = math.sqrt((i[0] - 0) ** 2 + (i[1] - 0) ** 2)
		heap = []
		heapq.heapify(heap)
		for i in list(dictionary.keys()):
			heapq.heappush(heap, (dictionary[i], i))
		result = []
		for i in range(K):
			result.append(heapq.heappop(heap)[1])
		return result


import math

class Solution:

	def __init__(self):
		self.dist_coord = dict()
		self.dist_heap = [None]
		self.final_result = list()

	def _calc_dist(self, x, y):
		return math.sqrt(x * x + y * y)

	def _calc_dist_coord(self):
		for point in self.coords:
			dist = self._calc_dist(point[0], point[1])
			if self.dist_coord.get(dist) is None:
				self.dist_coord[dist] = [point]
				self.dist_heap.append(dist)
			else:
				self.dist_coord[dist].append(point)

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		self.coords = points
		self._calc_dist_coord()
		for i in reversed(list(range(1, len(self.dist_heap) // 2 + 1))):
			self.shift_down(self.dist_heap, i)
		while K > 0 and len(self.dist_heap) > 1:
			for point in self.dist_coord[self.dist_heap[1]]:
				self.final_result.append(point)
				K -= 1
			self.del_elem_from_heap(self.dist_heap)
		return self.final_result

	def shift_up(self, h_list):
		i = len(h_list) - 1
		while int(i / 2) > 0:
			if h_list[i] > h_list[int(i / 2)]:
				(h_list[i], h_list[int(i / 2)]) = (h_list[int(i / 2)], h_list[i])
			i = int(i / 2)

	def shift_down(self, h_list, start):
		i = start
		l = 2 * i
		r = 2 * i + 1
		if l < len(h_list) and h_list[i] > h_list[l]:
			i = l
		if r < len(h_list) and h_list[i] > h_list[r]:
			i = r
		if i != start:
			(h_list[start], h_list[i]) = (h_list[i], h_list[start])
			self.shift_down(h_list, i)

	def add_elem_to_heap(self, h_list, val):
		h_list.append(val)
		self.shift_up(h_list)

	def del_elem_from_heap(self, h_list):
		h_list[1] = h_list[-1]
		h_list.pop()
		self.shift_down(h_list, 1)


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		n1 = len(points)
		newList = [0] * n1
		for i in range(n1):
			pointX = points[i][0]
			pointY = points[i][1]
			d2 = pointX * pointX + pointY * pointY
			newList[i] = d2
		newList.sort()
		res = newList[K - 1]
		i = 0
		t = 0
		ans = []
		while i < n1 and t < K:
			if res >= points[i][0] * points[i][0] + points[i][1] * points[i][1]:
				ans = ans + [points[i]]
				t += 1
			i += 1
		return ans


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def helper(p):
			return p[0] ** 2 + p[1] ** 2
		return sorted(points, key=helper)[:K]


from queue import PriorityQueue

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def dst(point):
			return (point[0] ** 2 + point[1] ** 2) ** (1 / 2)
		n = 0
		q = PriorityQueue()
		for point in points:
			point = [-dst(point)] + point[:]
			if n < K:
				q.put(point)
			else:
				least = q.get()
				if -point[0] < -least[0]:
					q.put(point)
				else:
					q.put(least)
			n += 1
		closest = []
		while not q.empty():
			closest.append(q.get()[1:])
		return closest


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		li = []

		class Point:

			def __init__(self, x, y):
				self.x = x
				self.y = y

			def distance_square(self):
				return self.x * self.x + self.y * self.y

			def __lt__(self, other):
				return self.distance_square() < other.distance_square()
		for p in points:
			x = p[0]
			y = p[1]
			pt = Point(x, y)
			heapq.heappush(li, pt)
		result_p = [heapq.heappop(li) for i in range(K)]
		result = [[p.x, p.y] for p in result_p]
		return result


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def get_distance(point):
			return point[0] ** 2 + point[1] ** 2

		def helper(i, j, K):
			if i >= j:
				return
			pivot_index = random.randint(i, j)
			(points[j], points[pivot_index]) = (points[pivot_index], points[j])
			mid = partition(i, j)
			if mid == K - 1:
				return
			elif mid < K - 1:
				helper(mid + 1, j, K)
			else:
				helper(i, mid - 1, K)

		def partition(i, j):
			(left, right) = (i, j)
			pivot_distance = get_distance(points[j])
			for k in range(left, right):
				if get_distance(points[k]) < pivot_distance:
					(points[i], points[k]) = (points[k], points[i])
					i += 1
			(points[i], points[j]) = (points[j], points[i])
			return i
		helper(0, len(points) - 1, K)
		return points[:K]


from queue import PriorityQueue

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		pq = PriorityQueue()
		for p in points:
			distance = -1 * (p[0] * p[0] + p[1] * p[1])
			if pq.qsize() < K:
				pq.put((distance, p))
			else:
				pq.put((distance, p))
				pq.get()
		ans = []
		while pq.qsize():
			(distance, p) = pq.get()
			ans.append(p)
		return ans


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def norm(point):
			return point[0] ** 2 + point[1] ** 2
		dis = []
		for point in points:
			dis.append(norm(point))
		(dis, points) = list(zip(*sorted(zip(dis, points))))
		res = []
		for i in range(K):
			res.append(points[i])
		return res


import heapq

def getDistance(point):
	return point[0] ** 2 + point[1] ** 2

class Solution:

	def swap(self, i, j):
		tmp = self.points[i]
		tmp_dist = self.dist[i]
		self.points[i] = self.points[j]
		self.points[j] = tmp
		self.dist[i] = self.dist[j]
		self.dist[j] = tmp_dist

	def partition(self, start, end, pivot):
		self.swap(0, pivot)
		left = 1
		right = end
		while left <= right:
			if self.dist[left] > self.dist[0]:
				self.swap(left, right)
				right -= 1
			else:
				left += 1
		self.swap(0, right)
		return right

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		n = len(points)
		if n <= K:
			return points
		self.points = points
		self.dist = []
		for i in range(n):
			self.dist.append(getDistance(points[i]))
		start = 0
		end = n - 1
		pivot = self.partition(0, n - 1, K)
		while pivot != K:
			if pivot < K:
				start = pivot + 1
			else:
				end = pivot - 1
			pivot = self.partition(start, end, start)
		res = []
		return self.points[0:K]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		d = {}
		ans = []
		points = sorted(points, key=lambda x: x[0] ** 2 + x[1] ** 2)
		for i in range(K):
			ans.append(points[i])
		return ans


import math

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		a = []
		for i in range(len(points)):
			a.append([math.sqrt(pow(points[i][0], 2) + pow(points[i][1], 2)), [points[i][0], points[i][1]]])
		a.sort(key=lambda x: x[0])
		print(a)
		l = []
		for j in range(K):
			l.append(a[j][1])
		return l


import heapq

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def distance(point):
			return point[0] ** 2 + point[1] ** 2
		return sorted(points, key=distance)[:K]


class Solution:

	def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
		from queue import PriorityQueue as pq
		distance_points = [(-1 * (x ** 2 + y ** 2) ** 0.5, [x, y]) for (x, y) in points]
		q = pq()
		for item in distance_points:
			if q.qsize() < k:
				q.put(item)
			else:
				(distance, _) = item
				popped = q.get()
				(popped_distance, _) = popped
				if distance > popped_distance:
					q.put(item)
				else:
					q.put(popped)
		return [q.get()[1] for _ in range(k)]


from heapq import heappop, heappush, heapify

class Solution:

	def distFromOrigin(self, x, y):
		return sqrt(x ** 2 + y ** 2)

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		heap = []
		for point in points:
			dist = self.distFromOrigin(point[0], point[1])
			if len(heap) == K:
				if dist < -heap[0][0]:
					heappop(heap)
					heappush(heap, (-dist, point))
			else:
				heappush(heap, (-dist, point))
		output = []
		for item in heap:
			output.append(item[1])
		return output


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		if not points or not K:
			return []
		distances = []
		disMap = defaultdict(list)
		maxKDis = float('-inf')
		for point in points:
			dis = (point[0] ** 2 + point[1] ** 2) ** 0.5
			disMap[dis].append(point)
			if len(distances) < K:
				distances.append(dis)
				maxKDis = max(maxKDis, dis)
			elif len(distances) >= K and dis < maxKDis:
				distances.sort()
				distances.pop()
				distances.append(dis)
				maxKDis = max(distances[-2:])
		res = []
		for dis in distances:
			res.extend(disMap[dis])
		return res[:K]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		point_distance = dict()
		distance_list = []
		for (x, y) in points:
			distance = sqrt(x ** 2 + y ** 2)
			heappush(distance_list, distance)
			if distance in list(point_distance.keys()):
				point_distance[distance].append([x, y])
			else:
				point_distance[distance] = [[x, y]]
		result = []
		while K > 0:
			tmp = point_distance[heappop(distance_list)]
			K -= len(tmp)
			result = result + tmp
		return result


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		heap = []
		for (x, y) in points:
			dis2 = x ** 2 + y ** 2
			if len(heap) < K:
				heapq.heappush(heap, (-dis2, (x, y)))
			elif -dis2 > heap[0][0]:
				heapq.heappop(heap)
				heapq.heappush(heap, (-dis2, (x, y)))
		ans = []
		for i in range(K):
			(x, y) = heapq.heappop(heap)[1]
			ans = [[x, y]] + ans
		return ans


from queue import PriorityQueue
import math

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		queue = PriorityQueue()
		for point in points:
			queue.put((math.sqrt(point[0] ** 2 + point[1] ** 2), point))
		ans = []
		for i in range(K):
			ans.append(queue.get()[1])
		return ans


from heapq import heappop, heappush, heapify

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		l1 = []
		l2 = []
		heapify(l1)
		for i in range(0, len(points)):
			heappush(l1, (-1 * (points[i][0] * points[i][0] + points[i][1] * points[i][1]), i))
			if len(l1) > K:
				heappop(l1)
		while len(l1) > 0:
			i = heappop(l1)
			l2.append(points[i[1]])
		return l2


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def distance(point):
			return (point[0] ** 2 + point[1] ** 2) ** 0.5

		def partition(left, right, pivot_index):
			pivot = points[pivot_index]
			(points[pivot_index], points[right]) = (points[right], points[pivot_index])
			store_index = left
			for i in range(left, right):
				if distance(points[i]) < distance(pivot):
					(points[store_index], points[i]) = (points[i], points[store_index])
					store_index += 1
			(points[store_index], points[right]) = (points[right], points[store_index])
			return store_index
		(left, right) = (0, len(points) - 1)
		while True:
			pivot_index = random.randint(left, right)
			M = partition(left, right, pivot_index)
			if M == K - 1:
				break
			elif M < K - 1:
				left = M + 1
			else:
				right = M - 1
		return points[:K]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		dist = lambda i: points[i][0] ** 2 + points[i][1] ** 2

		def quicksort(points, K):
			print(points, K)
			if not points:
				return
			pivot = points[-1]
			(l, r, m) = ([], [], [])
			for i in points:
				if dist(i) == dist(pivot):
					m.append(i)
				elif dist(i) < dist(pivot):
					l.append(i)
				else:
					r.append(i)
			if len(l) >= K:
				return quicksort(l, K)
			elif len(l) < K <= len(l) + len(m):
				return l + m[:K - len(l)]
			else:
				return l + m + quicksort(r, K - len(l) - len(m))
		return [points[i] for i in quicksort([i for i in range(len(points))], K)]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		self.sort(0, len(points) - 1, points, K)
		return points[:K]

	def getDistance(self, a):
		return a[0] ** 2 + a[1] ** 2

	def sort(self, l, r, points, K):
		if l >= r:
			return
		mid = self.partition(l, r, points)
		if mid - l + 1 < K:
			self.sort(mid + 1, r, points, K - (mid - l + 1))
		else:
			self.sort(l, mid - 1, points, K)

	def partition(self, i, j, points):
		pivot = self.getDistance(points[i])
		l = i
		r = j
		while True:
			while l <= r and self.getDistance(points[l]) <= pivot:
				l += 1
			while l <= r and self.getDistance(points[r]) > pivot:
				r -= 1
			if l >= r:
				break
			(points[l], points[r]) = (points[r], points[l])
		(points[i], points[r]) = (points[r], points[i])
		return r


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		if not points:
			return []

		def distance(x, y):
			return ((x - 0) ** 2 + (y - 0) ** 2) ** 0.5

		def binsea_insert(dist, point):
			if not nearest:
				nearest.append((dist, point))
				return
			(left, right) = (0, len(nearest) - 1)
			while left <= right:
				(d, coor) = nearest[right]
				if dist >= d:
					nearest.insert(right + 1, (dist, point))
					return
				(d, coor) = nearest[left]
				if dist <= d:
					nearest.insert(left, (dist, point))
					return
				mid = left + (right - left) // 2
				(d, coor) = nearest[mid]
				if dist < d:
					right = mid - 1
				else:
					left = mid + 1
		nearest = []
		for point in points:
			(x, y) = point
			binsea_insert(distance(x, y), point)
		print(nearest)
		results = []
		for k in range(K):
			if k < len(nearest):
				(d, point) = nearest[k]
				results.append(point)
		return results


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		heap = [(float('-Inf'), 0, 0)] * K
		for (x, y) in points:
			heapq.heappushpop(heap, (-x ** 2 - y ** 2, x, y))
		res = []
		while heap:
			(val, row, col) = heapq.heappop(heap)
			res.append([row, col])
		return res


from collections import defaultdict

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		dic = defaultdict(list)
		for i in range(len(points)):
			distance = points[i][0] ** 2 + points[i][1] ** 2
			dic[distance].append(points[i])
		dis_list = sorted(dic.keys())
		ans = []
		for i in dis_list:
			ans.extend(dic[i])
		return ans[:K]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		points = [[i ** 2 + j ** 2, i, j] for (i, j) in points]

		def quickSelect(l, r):
			p = l
			for i in range(l, r):
				if points[i][0] < points[r][0]:
					(points[p], points[i]) = (points[i], points[p])
					p += 1
			(points[r], points[p]) = (points[p], points[r])
			if p == K - 1:
				return
			elif p > K - 1:
				quickSelect(l, p - 1)
			else:
				quickSelect(p + 1, r)
		quickSelect(0, len(points) - 1)
		return [[i, j] for (_, i, j) in points[:K]]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		for i in range(len(points)):
			points[i].insert(0, (points[i][0] ** 2 + points[i][1] ** 2) ** 0.5)
		points.sort()
		ans = []
		for i in range(K):
			ans.append(points[i][1:])
		return ans


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		heap = []
		for (x, y) in points:
			if len(heap) < K:
				heapq.heappush(heap, [-(x * x + y * y), [x, y]])
			else:
				heapq.heappushpop(heap, [-(x * x + y * y), [x, y]])
		return [pair for (value, pair) in heap]


import math
from queue import PriorityQueue

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		pq = PriorityQueue()
		for point in points:
			dist = math.sqrt((0 - abs(point[0])) ** 2 + (0 - abs(point[1])) ** 2)
			pq.put((dist, tuple(point)))
		i = 0
		res = []
		while pq and i < K:
			res.append(pq.get()[1])
			i += 1
		return res


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		shuffle(points)
		distance_dict = dict()

		def distance(xy):
			xy = tuple(xy)
			if xy in distance_dict:
				return distance_dict[xy]
			ans = xy[0] ** 2 + xy[1] ** 2
			distance_dict[xy] = ans
			return ans

		def _quicksort(points, left, right):
			if left > right:
				return
			pivot = right
			lower = left
			for i in range(left, right):
				if distance(points[i]) <= distance(points[pivot]):
					(points[lower], points[i]) = (points[i], points[lower])
					lower = lower + 1
			pivot = lower
			(points[pivot], points[right]) = (points[right], points[pivot])
			if K - 1 <= pivot:
				_quicksort(points, left, pivot - 1)
			else:
				_quicksort(points, left, pivot - 1)
				_quicksort(points, pivot + 1, right)
			return
		_quicksort(points, 0, len(points) - 1)
		return points[:K]


import heapq

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		max_heap = []
		for i in range(len(points)):
			sqrt = points[i][0] ** 2 + points[i][1] ** 2
			heapq.heappush(max_heap, [sqrt, points[i]])
		res = []
		for i in range(K):
			temp = heapq.heappop(max_heap)
			res.append(temp[1])
		return res


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		heap = []
		output = []
		for i in range(len(points)):
			distance = points[i][0] ** 2 + points[i][1] ** 2
			heapq.heappush(heap, (distance, points[i]))
		for i in range(K):
			add = heapq.heappop(heap)
			output.append(add[1])
		return output


import random
import math

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		euclidean = lambda x: math.sqrt(x[0] ** 2 + x[1] ** 2)

		def topK(arr, l, r, k):
			if l >= r:
				return
			choice = random.randint(l, r)
			(arr[l], arr[choice]) = (arr[choice], arr[l])
			(tl, tr) = (l + 1, r)
			while tl <= tr:
				if euclidean(arr[tl]) < euclidean(arr[l]):
					tl += 1
					continue
				if euclidean(arr[tl]) >= euclidean(arr[l]):
					(arr[tl], arr[tr]) = (arr[tr], arr[tl])
					tr -= 1
					continue
			(arr[l], arr[tr]) = (arr[tr], arr[l])
			partition = tr
			if partition - l + 1 <= k:
				topK(arr, partition + 1, r, k - (partition - l + 1))
			else:
				topK(arr, l, partition - 1, k)
		topK(points, 0, len(points) - 1, K)
		return points[:K]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		distant = [[point, point[0] ** 2 + point[1] ** 2] for point in points]
		distant.sort(key=itemgetter(1))
		res = [distant[i][0] for i in range(K)]
		return res


class Solution:

	def calculateEuclidean(self, point):
		return point[0] ** 2 + point[1] ** 2

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		heap = []
		for point in points:
			heapq.heappush(heap, (-self.calculateEuclidean(point), point))
			if len(heap) > K:
				heapq.heappop(heap)
		return [point[1] for point in heap]


import heapq

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		arr = [(-1 * (p[0] ** 2 + p[1] ** 2), p) for p in points]
		heap = arr[:K]
		heapq.heapify(heap)
		for p in arr[K:]:
			heapq.heappushpop(heap, p)
		return [coord for (distance, coord) in heap]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		arr = self.sortPoints(points)
		return arr[:K]

	def sortPoints(self, points):
		if len(points) <= 1:
			return points
		mid = len(points) // 2
		left = self.sortPoints(points[:mid])
		right = self.sortPoints(points[mid:])
		return self.merge(left, right)

	def merge(self, left, right):
		(arr, i, j) = ([], 0, 0)
		while i < len(left) and j < len(right):
			(xLeft, yLeft) = (left[i][0], left[i][1])
			(xRight, yRight) = (right[j][0], right[j][1])
			leftDis = xLeft * xLeft + yLeft * yLeft
			rightDis = xRight * xRight + yRight * yRight
			if leftDis < rightDis:
				arr.append(left[i])
				i += 1
			elif rightDis < leftDis:
				arr.append(right[j])
				j += 1
			else:
				arr.append(left[i])
				arr.append(right[j])
				(i, j) = (i + 1, j + 1)
		while i < len(left):
			arr.append(left[i])
			i += 1
		while j < len(right):
			arr.append(right[j])
			j += 1
		return arr


import heapq

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		point_map = {}
		for point in points:
			point_map[point[0], point[1]] = point[0] ** 2 + point[1] ** 2
		return [list(k) for (k, v) in sorted(point_map.items(), key=lambda kv: kv[1])[:K]]


import heapq

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		add_index = [tup + [idx] for (tup, idx) in zip(points, list(range(len(points))))]
		print(add_index)
		sorted_by_second = sorted(add_index, key=lambda tup: sqrt(tup[1] ** 2 + tup[0] ** 2))
		res = []
		for i in range(K):
			res += [sorted_by_second[i][:2]]
		return res


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		squared = [round((x[0] ** 2 + x[1] ** 2) ** (1 / 2), 2) for x in points]
		self.heapSort(points, squared)
		result = []
		for i in range(K):
			result.append(points[i])
		return result

	def heapify(self, points, squared, n, i):
		largest = i
		l = 2 * i + 1
		r = 2 * i + 2
		if l < n and squared[l] > squared[largest]:
			largest = l
		if r < n and squared[r] > squared[largest]:
			largest = r
		if largest != i:
			(squared[largest], squared[i]) = (squared[i], squared[largest])
			(points[largest], points[i]) = (points[i], points[largest])
			self.heapify(points, squared, n, largest)

	def heapSort(self, points, squared):
		n = len(squared)
		for i in range(n // 2 - 1, -1, -1):
			self.heapify(points, squared, n, i)
		for i in range(n - 1, 0, -1):
			(squared[i], squared[0]) = (squared[0], squared[i])
			(points[i], points[0]) = (points[0], points[i])
			self.heapify(points, squared, i, 0)


import heapq

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		heap = []
		for p in points:
			dist = -(p[0] * p[0] + p[1] * p[1])
			heapq.heappush(heap, (dist, p[0], p[1]))
			if len(heap) > K:
				heapq.heappop(heap)
		res = [[p[1], p[2]] for p in heap]
		return res


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		pq = []
		for (x, y) in points:
			if len(pq) < K:
				heapq.heappush(pq, (-x * x - y * y, [x, y]))
			else:
				(small_distance, small_coordinate) = heapq.heappop(pq)
				if -x * x - y * y > small_distance:
					heapq.heappush(pq, (-x * x - y * y, [x, y]))
				else:
					heapq.heappush(pq, (small_distance, small_coordinate))
		return [_[1] for _ in pq]


import operator

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		res = []
		dict_m = {}
		for i in range(len(points)):
			pt = points[i]
			tmp = pt[0] ** 2 + pt[1] ** 2
			dict_m[i] = tmp
		sorted_m = sorted(list(dict_m.items()), key=operator.itemgetter(1))
		tmp = [t[0] for t in sorted_m]
		res = [points[tmp[i]] for i in range(K)]
		print(res)
		return res


class Solution:
	from collections import defaultdict

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		distDict = defaultdict(list)
		for point in points:
			dist = point[0] ** 2 + point[1] ** 2
			distDict[dist].append(point)
		sortedKey = sorted(distDict.keys())
		rst = []
		for key in sortedKey:
			numOfPairs = len(distDict[key])
			if numOfPairs < K:
				K -= numOfPairs
				rst += distDict[key]
			elif numOfPairs >= K:
				rst += distDict[key][:K]
				return rst


import random

class Solution:

	def kClosest(self, nums: List[List[int]], k: int) -> List[List[int]]:
		dist = []
		for i in range(len(nums)):
			dist.append(nums[i][0] ** 2 + nums[i][1] ** 2)
		hMap = {}
		for i in range(len(dist)):
			hMap[i] = dist[i]
		unique_ids = list(hMap.keys())

		def helper(unique_ids, k, start, end):
			if start >= end:
				return
			pivot_idx = random.randint(start, end)
			(unique_ids[start], unique_ids[pivot_idx]) = (unique_ids[pivot_idx], unique_ids[start])
			pivot = hMap[unique_ids[start]]
			smaller = start
			for bigger in range(start + 1, end + 1):
				if hMap[unique_ids[bigger]] <= pivot:
					smaller += 1
					(unique_ids[smaller], unique_ids[bigger]) = (unique_ids[bigger], unique_ids[smaller])
			(unique_ids[start], unique_ids[smaller]) = (unique_ids[smaller], unique_ids[start])
			if k == smaller:
				return
			elif k < smaller:
				helper(unique_ids, k, start, smaller - 1)
			else:
				helper(unique_ids, k, smaller + 1, end)
		helper(unique_ids, k, 0, len(unique_ids) - 1)
		return [nums[i] for i in unique_ids[:k]]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		pq = []

		def distance(point):
			return point[0] * point[0] + point[1] * point[1]
		for (index, point) in enumerate(points):
			heapq.heappush(pq, (distance(point), index, point))
		ans = []
		k = 0
		while pq and k < K:
			(_, _, point) = heapq.heappop(pq)
			ans.append(point)
			k += 1
		return ans


from heapq import *

class Solution:

	def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
		maxHeap = []
		for i in range(k):
			heappush(maxHeap, [-self.distance(points[i]), points[i]])
		for j in range(k, len(points)):
			if maxHeap[0][0] < -self.distance(points[j]):
				heappop(maxHeap)
				heappush(maxHeap, [-self.distance(points[j]), points[j]])
		return [points for (distance, points) in list(maxHeap)]

	def distance(self, coord):
		return coord[0] ** 2 + coord[1] ** 2


import heapq

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		ans = []
		min_heap = []
		for pnt in points:
			heapq.heappush(min_heap, (pnt[0] ** 2 + pnt[1] ** 2, pnt))
		for i in range(K):
			ans.append(heapq.heappop(min_heap)[1])
		return ans


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		heap = []
		for (i, p) in enumerate(points):
			(x, y) = p
			dist = x ** 2 + y ** 2
			heapq.heappush(heap, (-dist, i))
			if len(heap) > K:
				heapq.heappop(heap)
		res = []
		for (_, i) in heap:
			res.append(points[i])
		return res


import heapq

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def get_distance(points):
			return sqrt(points[0] ** 2 + points[1] ** 2)
		dist = [[get_distance(point), point] for point in points]
		heapq.heapify(dist)
		ans = []
		for i in range(K):
			ans.append(heapq.heappop(dist)[1])
		return ans


from heapq import *

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		hp = []
		n = len(points)
		if K >= n:
			return points
		if K == 0:
			return []
		for (x, y) in points:
			key = -(x ** 2 + y ** 2)
			if len(hp) < K:
				heappush(hp, (key, x, y))
			elif -hp[0][0] > -key:
				heappop(hp)
				heappush(hp, (key, x, y))
		ans = []
		for _ in range(K):
			(key, x, y) = heappop(hp)
			ans.append([x, y])
		return ans


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		nums = []
		heapq.heapify(nums)

		def dist(x, y):
			return (x ** 2 + y ** 2) ** 0.5
		for (x, y) in points:
			heapq.heappush(nums, (-dist(x, y), [x, y]))
			if len(nums) > K:
				heapq.heappop(nums)
		return [k[1] for k in nums]


from collections import defaultdict
from heapq import heapify, heappush, heappop

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		temp = []
		for i in points:
			dist = i[0] ** 2 + i[1] ** 2
			temp.append([dist, [i[0], i[1]]])
		heapify(temp)
		res = []
		for i in range(K):
			res.append(heappop(temp)[1])
		return res


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def edistance(point):
			d = sqrt(point[0] ** 2 + point[1] ** 2)
			return d
		result = []
		stk = []
		for point in points:
			dis = edistance(point)
			heapq.heappush(stk, [dis, point])
		while K > 0:
			result.append(heapq.heappop(stk)[1])
			K -= 1
		return result


from math import sqrt

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		sqrt_d = {}
		for (x, y) in points:
			sqrt_d[x, y] = sqrt(x ** 2 + y ** 2)
		return heapq.nsmallest(K, sqrt_d, key=lambda x: sqrt_d[x])


import math
import heapq

class Solution:

	def getEuclideanDistance(self, p1):
		return math.sqrt(p1[0] ** 2 + p1[1] ** 2)

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		kheap = []
		heapq.heapify(kheap)
		size = 0
		for (i, point) in enumerate(points):
			heapq.heappush(kheap, (-self.getEuclideanDistance(point), i))
			size += 1
			if size > K:
				heapq.heappop(kheap)
		kpoints = []
		while kheap:
			(dist, ind) = heapq.heappop(kheap)
			kpoints.append(points[ind])
		return kpoints


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		h = []
		for point in points:
			d = 0
			for cor in point:
				d += cor ** 2
			h.append((d, point))
		ksmallests = heapq.nsmallest(K, h)
		ret = []
		for (val, point) in ksmallests:
			ret.append(point)
		return ret


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		heap = []
		indices = {}
		for i in range(len(points)):
			curr_point = points[i]
			distance = math.sqrt(curr_point[0] ** 2 + curr_point[1] ** 2)
			heapq.heappush(heap, distance)
			if distance in list(indices.keys()):
				indices[distance].append(i)
			else:
				indices[distance] = [i]
		result = []
		i = 0
		while i < K:
			curr_distance = heapq.heappop(heap)
			curr_indices = indices[curr_distance]
			for index in curr_indices:
				result.append(points[index])
				i += 1
		return result


from collections import defaultdict
import math
import heapq

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		heap = []
		lookup = defaultdict(list)
		for (x, y) in points:
			distance = math.sqrt(x ** 2 + y ** 2)
			lookup[distance].append([x, y])
			heapq.heappush(heap, -distance)
			if len(heap) > K:
				heapq.heappop(heap)
		result = []
		for distance in heap:
			result.append(lookup[-distance].pop())
		return result


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		heap = []
		for (a, b) in points:
			if len(heap) < K:
				heapq.heappush(heap, (-1 * (a ** 2 + b ** 2), [a, b]))
			else:
				heapq.heappushpop(heap, (-1 * (a ** 2 + b ** 2), [a, b]))
		op = []
		print(heap)
		for i in range(K):
			print(i)
			op.append(heap[i][1])
		return op


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		length = len(points)
		if length <= K:
			return points
		distances: Dict[int, List[int]] = defaultdict(list)
		for (i, li) in enumerate(points):
			distance = (li[0] ** 2 + li[1] ** 2) ** 0.5
			distances[distance].append(i)
		order = OrderedDict(sorted(distances.items()))
		ans = []
		for (i, (key, value)) in enumerate(order.items()):
			for j in value:
				ans.append(points[j])
			if len(ans) >= K:
				break
		return ans[:K]


class myObj:

	def __init__(self, val, p):
		self.val = val
		self.p = p

	def __lt__(self, other):
		return self.val < other.val

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def partition(arr, left, right):
			i = left
			for j in range(left, right):
				if arr[j] < arr[right]:
					(arr[i], arr[j]) = (arr[j], arr[i])
					i += 1
			(arr[i], arr[right]) = (arr[right], arr[i])
			return i

		def sort(arr, left, right, K):
			if left < right:
				p = partition(arr, left, right)
				if p == K:
					return
				elif p < K:
					sort(arr, p + 1, right, K)
				else:
					sort(arr, left, p - 1, K)
		dis = [0] * len(points)
		for i in range(len(points)):
			dis[i] = myObj(points[i][0] * points[i][0] + points[i][1] * points[i][1], points[i])
		sort(dis, 0, len(points) - 1, K)
		ans = []
		for i in range(K):
			ans.append(dis[i].p)
		return ans


from scipy.spatial import distance

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		points.sort(key=lambda P: P[0] ** 2 + P[1] ** 2)
		return points[:K]


class Point:

	def __init__(self, pt):
		self.distance = -1 * sqrt(pt[0] ** 2 + pt[1] ** 2)
		self.pt = pt

	def __lt__(self, other):
		return self.distance < other.distance

	def __eq__(self, other):
		return self.distance == other.distance

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		heap = []
		heapq.heapify(heap)
		for pt in points:
			curr_pt = Point(pt)
			if len(heap) < K:
				heapq.heappush(heap, curr_pt)
			else:
				heapq.heappushpop(heap, curr_pt)
		return [pt.pt for pt in heap]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		self.quickselect(points, K, 0, len(points) - 1)
		return points[:K]

	def quickselect(self, points, k, lo, high):
		if lo >= high:
			return
		pivot = self.partition(points, lo, high)
		if pivot + 1 == k:
			return
		elif pivot < k:
			self.quickselect(points, k, pivot + 1, high)
		else:
			self.quickselect(points, k, lo, pivot - 1)

	def partition(self, points, lo, high):
		pivot = self.dist(points[high])
		w = lo
		for r in range(lo, high):
			if self.dist(points[r]) < pivot:
				(points[w], points[r]) = (points[r], points[w])
				w += 1
		(points[w], points[high]) = (points[high], points[w])
		return w

	def dist(self, pt):
		return pt[0] ** 2 + pt[1] ** 2


class Solution:

	def partition(self, nums, l, r):
		pivot = nums[r]
		i = l - 1
		for j in range(l, r):
			if nums[j] <= pivot:
				i += 1
				(nums[i], nums[j]) = (nums[j], nums[i])
		(nums[i + 1], nums[r]) = (nums[r], nums[i + 1])
		return i + 1

	def selectSort(self, nums, l, r, k):
		if l < r:
			p = self.partition(nums, l, r)
			if p == k:
				return
			elif k < p:
				self.selectSort(nums, l, p - 1, k)
			else:
				self.selectSort(nums, p + 1, r, k)

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		dists = [math.sqrt(p[0] ** 2 + p[1] ** 2) for p in points]
		self.selectSort(dists, 0, len(dists) - 1, K)
		print(dists)
		out = []
		if K == len(points):
			return points
		for p in points:
			if math.sqrt(p[0] ** 2 + p[1] ** 2) < dists[K]:
				out.append(p)
		return out


class Solution:
	import math

	def distance(self, point):
		return math.sqrt(point[0] ** 2 + point[1] ** 2)

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		distances = {}
		for point in points:
			distances[tuple(point)] = self.distance(point)
		print(distances)
		points_sorted = sorted(list(distances.keys()), key=lambda x: distances[x])
		return [list(i) for i in points_sorted[:K]]


from numpy import argsort
from numpy import array
from numpy import sqrt
from numpy import sum

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		p = array(points)
		q = sqrt(sum(p ** 2, axis=1))
		return p[argsort(q)[:K]]


from collections import OrderedDict

class Solution:

	def partition(self, nums, l, r):
		piv = nums[r]
		i = l - 1
		for j in range(l, r):
			if nums[j] <= piv:
				i += 1
				(nums[i], nums[j]) = (nums[j], nums[i])
		(nums[r], nums[i + 1]) = (nums[i + 1], nums[r])
		return i + 1

	def selectSort(self, nums, left, right, k):
		if left < right:
			p = self.partition(nums, left, right)
			if p == k:
				return
			elif k < p:
				self.selectSort(nums, left, p - 1, k)
			else:
				self.selectSort(nums, p + 1, right, k)

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		dists = [math.sqrt(p[0] ** 2 + p[1] ** 2) for p in points]
		self.selectSort(dists, 0, len(dists) - 1, K)
		print(dists)
		out = []
		if K == len(points):
			return points
		for p in points:
			if math.sqrt(p[0] ** 2 + p[1] ** 2) < dists[K]:
				out.append(p)
		return out


import heapq

class Distance:

	def __init__(self, p, d):
		self.d = d
		self.p = p

	def __lt__(self, other):
		return self.d >= other.d

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def distance(p):
			return math.sqrt(p[0] ** 2 + p[1] ** 2)
		distances_k = []
		for p in points:
			d = Distance(p, distance(p))
			if len(distances_k) < K:
				heapq.heappush(distances_k, d)
			elif d.d < distances_k[0].d:
				heapq.heappop(distances_k)
				heapq.heappush(distances_k, d)
		return [x.p for x in distances_k]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		K -= 1
		(start, end) = (0, len(points) - 1)
		while start <= end:
			mid = self.__partition(points, start, end)
			if mid == K:
				break
			elif mid < K:
				start = mid + 1
			else:
				end = mid - 1
		return points[:K + 1]

	def __partition(self, points, lo, hi):
		__dist = lambda points, i: points[i][0] ** 2 + points[i][1] ** 2
		d = __dist(points, lo)
		(i, j) = (lo, hi + 1)
		while True:
			while i < hi and __dist(points, i + 1) < d:
				i += 1
			while j > lo and __dist(points, j - 1) > d:
				j -= 1
			(i, j) = (i + 1, j - 1)
			if i >= j:
				break
			(points[i], points[j]) = (points[j], points[i])
		(points[lo], points[j]) = (points[j], points[lo])
		return j


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def parition(st, end):
			(lo, i, j) = (st, st, end)
			while True:
				while i < end and arr[i][0] <= arr[lo][0]:
					i += 1
				while j > st and arr[lo][0] <= arr[j][0]:
					j -= 1
				if i >= j:
					break
				(arr[i], arr[j]) = (arr[j], arr[i])
			(arr[lo], arr[j]) = (arr[j], arr[lo])
			return j

		def quick_select(st, end):
			if st > end:
				return
			par = parition(st, end)
			if par == K:
				return
			if par > K:
				quick_select(st, par - 1)
			else:
				quick_select(par + 1, end)
			return
		arr = []
		for pt in points:
			arr.append([math.sqrt(sum([x ** 2 for x in pt])), pt])
		random.shuffle(arr)
		quick_select(0, len(arr) - 1)
		return [x[1] for x in arr[:K]]


import math
import heapq

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		sol = []
		for point in points:
			dist = math.sqrt(point[0] ** 2 + point[1] ** 2)
			heapq.heappush(sol, (dist, point))
		print(sol)
		return [point[1] for point in heapq.nsmallest(K, sol)]


import math

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		if len(points) == 0:
			return []
		points.sort(key=lambda x: math.sqrt(x[0] * x[0] + x[1] * x[1]))
		return points[:K]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def distance(point):
			(x, y) = point
			return x ** 2 + y ** 2
		distances = [(distance(p), p) for p in points]
		heapq.heapify(distances)
		for point in points:
			heapq.heappushpop(distances, (-distance(point), point))
		return [p for (_, p) in heapq.nsmallest(K, distances)]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		left = 0
		right = len(points) - 1
		target = K - 1
		while left <= right:
			rand_pivot = random.randint(left, right)
			pivot = self.partition(left, right, rand_pivot, points)
			if pivot == target:
				return points[0:pivot + 1]
			elif pivot < target:
				left = pivot + 1
			else:
				right = pivot - 1

	def partition(self, i, j, pivot, arr):
		pivot_element = self.distFromOrigin(arr[pivot])
		self.swap(pivot, j, arr)
		result = i
		for x in range(i, j):
			if self.distFromOrigin(arr[x]) < pivot_element:
				self.swap(x, result, arr)
				result += 1
		self.swap(result, j, arr)
		return result

	def swap(self, i, j, arr):
		temp = arr[i]
		arr[i] = arr[j]
		arr[j] = temp

	def distFromOrigin(self, point):
		return math.sqrt(point[0] ** 2 + point[1] ** 2)


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def getDistance(p: List[int]):
			return p[0] ** 2 + p[1] ** 2

		def helper(points: List[List[int]], K: int):
			if len(points) == K:
				return points
			(left, right) = ([], [])
			import random
			random.shuffle(points)
			pivot = points[0][0]
			for point in points:
				curr_distance = point[0]
				if curr_distance > pivot:
					right.append(point)
				else:
					left.append(point)
			if len(left) >= K:
				return helper(left, K)
			else:
				return left + helper(right, K - len(left))
		distances = []
		for point in points:
			distances.append([getDistance(point), point])
		top_results = helper(distances, K)
		for (i, result) in enumerate(top_results):
			top_results[i] = result[1]
		return top_results


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def dist(point):
			return sum([e ** 2 for e in point])

		def partition(nums, left, right):
			x = dist(nums[right])
			i = left - 1
			for j in range(left, right):
				if dist(nums[j]) < x:
					i += 1
					(nums[i], nums[j]) = (nums[j], nums[i])
			i += 1
			(nums[right], nums[i]) = (nums[i], nums[right])
			return i
		p = -1
		left = 0
		right = len(points) - 1
		while p != K:
			p = partition(points, left, right)
			if p + 1 < K:
				left = p + 1
			elif p + 1 > K:
				right = p - 1
			else:
				return points[:K]
		return points[:K]


from heapq import *

class Point:

	def __init__(self, x, y):
		self.x = x
		self.y = y
		self.distance = x ** 2 + y ** 2

	def __lt__(self, other):
		return self.distance > other.distance

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		distance_heap = []
		for (x, y) in points:
			if len(distance_heap) >= K:
				if Point(x, y) > distance_heap[0]:
					heappop(distance_heap)
					heappush(distance_heap, Point(x, y))
			else:
				heappush(distance_heap, Point(x, y))
		res = []
		while distance_heap:
			point = heappop(distance_heap)
			res.append([point.x, point.y])
		return res


class myObj:

	def __init__(self, val, p):
		self.val = val
		self.p = p

	def __lt__(self, other):
		return self.val > other.val

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		h = []
		heapq.heapify(h)
		for p in points:
			dis = p[0] * p[0] + p[1] * p[1]
			heapq.heappush(h, myObj(dis, p))
			if len(h) > K:
				heapq.heappop(h)
		ans = []
		while h:
			obj = heapq.heappop(h)
			ans.append(obj.p)
		return ans


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		self.countK(points, 0, len(points) - 1, K)
		return points[:K]

	def countK(self, points, l, r, k):
		if l < r:
			p = self.createPartition(points, l, r, k)
			if p == k:
				return
			elif p < k:
				self.countK(points, p + 1, r, k)
			else:
				self.countK(points, l, p - 1, k)

	def createPartition(self, points, l, r, k):
		pivot = points[r]
		count = l
		for i in range(l, r):
			if points[i][0] ** 2 + points[i][1] ** 2 <= pivot[0] ** 2 + pivot[1] ** 2:
				(points[i], points[count]) = (points[count], points[i])
				count += 1
		(points[count], points[r]) = (points[r], points[count])
		return count


from queue import PriorityQueue

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		pq = PriorityQueue()
		for (i, c) in enumerate(points):
			pq.put((c[0] * c[0] + c[1] * c[1], i))
		res = []
		for j in range(K):
			pair = pq.get()
			res.append(points[pair[1]])
		return res


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		return sorted(points, key=lambda point: point[0] * point[0] + point[1] * point[1])[:K]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		self.qkSel(points, 0, len(points) - 1, K)
		return points[:K]

	def qkSel(self, points, l, r, K):
		if l > r:
			return
		idx = random.randint(l, r)
		(points[idx], points[r]) = (points[r], points[idx])
		i = l
		for j in range(l, r):
			if self.cmp(points[j], points[r]):
				(points[i], points[j]) = (points[j], points[i])
				i += 1
		(points[i], points[r]) = (points[r], points[i])
		if i == K:
			return
		elif i < K:
			return self.qkSel(points, i + 1, r, K)
		elif i > K:
			return self.qkSel(points, l, i - 1, K)

	def cmp(self, p1, p2):
		return p1[0] ** 2 + p1[1] ** 2 - (p2[0] ** 2 + p2[1] ** 2) < 0


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		dist = lambda x: math.sqrt(points[x][0] ** 2 + points[x][1] ** 2)

		def dc(i, j, K):
			if i >= j:
				return
			(oi, oj) = (i, j)
			i += 1
			pivot = dist(oi)
			while True:
				while i < j and dist(i) < pivot:
					i += 1
				while i <= j and dist(j) >= pivot:
					j -= 1
				if i >= j:
					break
				(points[i], points[j]) = (points[j], points[i])
			(points[oi], points[j]) = (points[j], points[oi])
			if K - 1 == j:
				return
			elif K - 1 < j:
				dc(oi, j, K)
			else:
				dc(j + 1, oj, K)
		dc(0, len(points) - 1, K)
		return points[:K]


class MyHeapObj:

	def __init__(self, x, y, dist):
		self.x = x
		self.y = y
		self.dist = dist

	def __gt__(self, other):
		return self.dist > other.dist
import heapq

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		pointsHeap = []
		for p in points:
			dist = (p[0] ** 2 + p[1] ** 2) ** 0.5
			heapq.heappush(pointsHeap, MyHeapObj(p[0], p[1], dist))
		ret = []
		for i in range(K):
			point = heapq.heappop(pointsHeap)
			ret.append([point.x, point.y])
		return ret


import random

class Solution:

	def _value(self, point):
		return point[0] ** 2 + point[1] ** 2

	def _quickSelect(self, start: int, end: int, points: List[List[int]]) -> int:
		if start == end:
			return start
		p = random.randint(start, end)
		(points[p], points[start]) = (points[start], points[p])
		j = start + 1
		for i in range(start + 1, end + 1):
			if self._value(points[i]) <= self._value(points[start]):
				(points[i], points[j]) = (points[j], points[i])
				j += 1
		(points[j - 1], points[start]) = (points[start], points[j - 1])
		return j - 1

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		start = 0
		end = len(points) - 1
		while True:
			p = self._quickSelect(start, end, points)
			if p < K - 1:
				start = p + 1
			elif p > K - 1:
				end = p - 1
			else:
				return points[:p + 1]
		return None


class Solution:

	def kClosest(self, points, K):
		self.sort(points, 0, len(points) - 1, K)
		return points[:K]

	def sort(self, points, l, r, K):
		if l < r:
			p = self.partition(points, l, r)
			if p == K:
				return
			elif p < K:
				self.sort(points, p + 1, r, K)
			else:
				self.sort(points, l, p - 1, K)

	def partition(self, points, l, r):
		pivot = points[r]
		a = l
		for i in range(l, r):
			if points[i][0] ** 2 + points[i][1] ** 2 <= pivot[0] ** 2 + pivot[1] ** 2:
				(points[a], points[i]) = (points[i], points[a])
				a += 1
		(points[a], points[r]) = (points[r], points[a])
		return a


class Solution:

	def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:

		def distance(point):
			return point[0] ** 2 + point[1] ** 2

		def find_pivot_index(low, high, p_index):
			ppoint = points[p_index]
			(points[p_index], points[high]) = (points[high], points[p_index])
			i = low
			j = low
			while j < high:
				if distance(points[j]) < distance(points[high]):
					(points[i], points[j]) = (points[j], points[i])
					i += 1
				j += 1
			(points[i], points[high]) = (points[high], points[i])
			return i

		def recursion(low, high):
			pivot_index = random.randint(low, high)
			p = find_pivot_index(low, high, pivot_index)
			if p == k - 1:
				return points[:p + 1]
			elif p < k - 1:
				return recursion(p + 1, high)
			else:
				return recursion(low, p - 1)
		return recursion(0, len(points) - 1)


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		res = []

		def insert(d, pos):
			l = 0
			r = len(res)
			while l < r:
				mid = (l + r) // 2
				if res[mid][0] > d:
					r = mid
				else:
					l = mid + 1
			res.insert(l, [d, pos])
			Max = res[-1][0]
		Max = float('inf')
		for i in range(len(points)):
			dis = points[i][0] ** 2 + points[i][1] ** 2
			print(len(res))
			if i > K:
				res.pop()
			insert(dis, points[i])
		ans = []
		for i in range(K):
			ans.append(res[i][1])
		return ans


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		dist = lambda x: x[0] ** 2 + x[1] ** 2

		def partition(start, end):
			ran = random.randint(start, end)
			pivot = end
			(points[pivot], points[ran]) = (points[ran], points[pivot])
			border = start
			for cur in range(start, end):
				if dist(points[cur]) <= dist(points[pivot]):
					(points[cur], points[border]) = (points[border], points[cur])
					border += 1
			(points[border], points[pivot]) = (points[pivot], points[border])
			return border

		def quick_sort(left, right, k):
			if left >= right:
				return
			p = partition(left, right)
			if p == k - 1:
				return
			if p < k - 1:
				quick_sort(p + 1, right, k)
			else:
				quick_sort(left, p - 1, k)
		quick_sort(0, len(points) - 1, K)
		return points[:K]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

		def dist(x) -> int:
			return x[0] ** 2 + x[1] ** 2

		def partition(i, j) -> int:
			pivot = points[j]
			l = i - 1
			for r in range(i, j):
				rv = points[r]
				if dist(rv) < dist(pivot):
					l += 1
					(points[l], points[r]) = (points[r], points[l])
			(points[j], points[l + 1]) = (points[l + 1], points[j])
			return l + 1

		def sort(i, j, K):
			if i >= j:
				return
			mid = partition(i, j)
			if mid - i + 1 == K:
				return
			elif mid - i + 1 < K:
				sort(mid + 1, j, K - (mid - i + 1))
			else:
				sort(i, mid - 1, K)
		sort(0, len(points) - 1, K)
		return points[:K]


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		(start, end) = (0, len(points) - 1)
		pivot = -1
		while start <= end:
			pivot = self.partition(points, start, end)
			if pivot == K:
				return points[0:pivot]
			elif pivot > K:
				end = pivot - 1
			else:
				start = pivot + 1
		return points

	def partition(self, points, start, end):
		pivot = start
		for i in range(start, end + 1):
			if self.dist(points, i) < self.dist(points, end):
				(points[i], points[pivot]) = (points[pivot], points[i])
				pivot += 1
		(points[end], points[pivot]) = (points[pivot], points[end])
		return pivot

	def dist(self, points, i):
		return points[i][0] ** 2 + points[i][1] ** 2


import math
import heapq

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		if len(points) == 0:
			return []
		if K >= len(points):
			return points

		def euclidean(point):
			(x, y) = point
			return math.sqrt(math.pow(x, 2) + math.pow(y, 2))
		mod_points = []
		for point in points:
			dist = euclidean(point)
			mod_points.append((dist, point[0], point[1]))
		heapq.heapify(mod_points)
		ret_values = heapq.nsmallest(K, mod_points)
		ret_values = [[x, y] for (dist, x, y) in ret_values]
		return ret_values


class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		max_heap = []
		for point in points:
			(x, y) = (point[0], point[1])
			dist = x ** 2 + y ** 2
			if len(max_heap) < K:
				heapq.heappush(max_heap, (-dist, x, y))
			elif dist < -max_heap[0][0]:
				heapq.heappop(max_heap)
				heapq.heappush(max_heap, (-dist, x, y))
		return [[x, y] for (dist, x, y) in max_heap]


class Solution(object):

	def kClosest(self, points, K):

		def distance(p):
			return (p[0] ** 2 + p[1] ** 2) ** 0.5

		def partition(l, r):
			pivot = points[r]
			mover = l
			for i in range(l, r):
				if distance(points[i]) <= distance(pivot):
					(points[mover], points[i]) = (points[i], points[mover])
					mover += 1
			(points[mover], points[r]) = (points[r], points[mover])
			return mover

		def sort(l, r):
			if l < r:
				p = partition(l, r)
				if p == K:
					return
				elif p < K:
					sort(p + 1, r)
				else:
					sort(l, p - 1)
		sort(0, len(points) - 1)
		return points[:K]


class Node:

	def __init__(self, x, y, d=None):
		self.x = x
		self.y = y
		if d:
			self.distance = d
		else:
			self.distance = x * x + y * y

def parent(i):
	return (i - 1) // 2

def left(i):
	return 2 * i + 1

def right(i):
	return 2 * i + 2

def swap(heap, i, j):
	t = heap[i]
	heap[i] = heap[j]
	heap[j] = t

def heapify(heap):
	n = len(heap)
	for i in range(1, n):
		p = parent(i)
		while i > 0 and heap[p].distance < heap[i].distance:
			swap(heap, i, p)
			i = p
			p = parent(i)

def replace_top(heap, node):
	t = heap[0]
	heap[0] = node
	n = len(heap)
	i = 0
	l = left(i)
	r = right(i)
	while i < n and (not ((l >= n or heap[l].distance <= heap[i].distance) and (r >= n or heap[r].distance <= heap[i].distance))):
		if l < n and r < n:
			if heap[l].distance < heap[r].distance:
				swap(heap, i, r)
				i = r
			else:
				swap(heap, i, l)
				i = l
		elif l < n:
			swap(heap, i, l)
			i = l
		else:
			swap(heap, i, r)
			i = r
		l = left(i)
		r = right(i)

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
		n = len(points)
		heap = []
		for i in range(K):
			p = points[i]
			node = Node(p[0], p[1])
			heap.append(node)
		heapify(heap)
		top = 0
		for i in range(K, n):
			p = points[i]
			distance = p[0] * p[0] + p[1] * p[1]
			if heap[top].distance > distance:
				node = Node(p[0], p[1], distance)
				replace_top(heap, node)
		return [[heap[i].x, heap[i].y] for i in range(K)]


import random

class Solution:

	def kClosest(self, points: List[List[int]], K: int) -> int:
		(l, h, k) = (0, len(points) - 1, K - 1)
		dist = lambda i: points[i][0] ** 2 + points[i][1] ** 2

		def partition(l: int, h: int) -> int:
			t = random.randint(l, h)
			(points[t], points[h]) = (points[h], points[t])
			for (i, val) in enumerate(points[l:h + 1], l):
				if dist(i) < dist(h):
					(points[i], points[l]) = (points[l], points[i])
					l += 1
			(points[l], points[h]) = (points[h], points[l])
			return l
		while True:
			pos = partition(l, h)
			if pos < k:
				l = pos + 1
			elif pos > k:
				h = pos - 1
			else:
				return points[:K]