K Closest Points to Origin — Leetcode Medium

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]].
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.)
  1. -10000 < points[i][0] < 10000
  2. -10000 < points[i][1] < 10000

Approach 2: Divide and Conquer

Intuition

def kClosest(self, points, K):    dist = lambda i: points[i][0]**2 + points[i][1]**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[0]**2 + P[1]**2)
return points[:K]
  • Space Complexity: O(N).

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store