# K Closest Points to Origin — Leetcode Medium

`Input: points = [[1,3],[-2,2]], K = 1Output: [[-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]].`
`Input: points = [[3,3],[5,-1],[-2,4]], K = 2Output: [[3,3],[-2,4]](The answer [[-2,4],[3,3]] would also be accepted.)`
1. `-10000 < points[i] < 10000`
2. `-10000 < points[i] < 10000`

## Approach 2: Divide and Conquer

Intuition

`def kClosest(self, points, K):    dist = lambda i: points[i]**2 + points[i]**2    # Quick sort partitioning using Horre's partitioning    def partition(i, j):        # Partition by pivot A[i], returning an index mid        # such that A[i] <= A[mid] <= A[j] for i < mid < j.        pi = 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            # swap where the dist(i) > pivot and dist(j) < pivot            points[i], points[j] = points[j], points[i]# Myself: Now all points upto the jth are smaller than pivot        # move the pivot to j and return pivot's index which is j.        points[pi], points[j] = points[j], points[pi]                return j            def sort(i, j, K):        # Partially sorts A[i:j+1] so the first K elements are        # the smallest K elements.        if i >= j: return        # Put random element as A[i] - this is the pivot        k = random.randint(i, j)        points[i], points[k] = points[k], points[i]        pi = partition(i, j)        if K < pi - i + 1:             sort(i, pi - 1, K)        elif K > pi - i + 1:             # Notice how we reduced K to K - (pi - i +1)             sort(pi + 1, j, K - (pi - i + 1))    sort(0, len(points) - 1, K)    # our purpose is the ensure all k closest elements are    # included in the first K positions. So We do QuickSelect till out pivot is at the Kth position. Then we quit.    return points[:K]`
• Space Complexity: O(N).

## Approach 1: Sort

Intuition

`class Solution(object):    def kClosest(self, points, K):        points.sort(key = lambda P: P**2 + P**2)        return points[:K]`
• Space Complexity: O(N).

--

--