LeetMotion
You are given an 2-D array points where points[i] = [xi, yi] represents the coordinates of a point on an X-Y axis plane. You are also given an integer k.
Return the k closest points to the origin (0, 0).
The distance between two points is defined as the Euclidean distance (sqrt((x1 - x2)^2 + (y1 - y2)^2)).
You may return the answer in any order.
The distance between (0, 2) and the origin (0, 0) is 2. The distance between (2, 2) and the origin is sqrt(2^2 + 2^2) = 2.82842. So the closest point to the origin is (0, 2).
1 <= k <= points.length <= 1000-100 <= points[i][0], points[i][1] <= 100Why do it this way? If you sort all points based on their distance to the origin, the k closest points will simply be the first k elements of the array. It's the most trivial approach, but inefficient if N is massive and k is very small because you waste time fully sorting elements you don't even need to look at.
If you want to invite your 5 closest friends to dinner, you don't need to rank every single person you've ever met from closest to least close. Sorting the whole list is overkill when you only care about the top 5.
function kClosest(points, k):
points.sort(by_key=lambda p: p.x^2 + p.y^2)
return points[0:k]Why do it this way? You can throw all points into a Min-Heap based on their distance. Building the heap takes O(N). Then, you just pop from the heap exactly `k` times. Since popping takes O(log N), it's faster than sorting the entire array if `k` is small compared to `N`.
You dump all your emails into an inbox that automatically bubbles the most important ones to the top. Instead of fully sorting your entire inbox to perfection, you just pull the top 5 most important emails one by one.
function kClosest(points, k):
minHeap = []
for p in points:
minHeap.push((p.x^2 + p.y^2, p))
heapify(minHeap)
result = []
for i from 1 to k:
result.push(heappop(minHeap).point)
return resultWhy do it this way? Instead of storing all `N` points in memory, we only keep exactly `k` points in a Max-Heap. The Max-Heap keeps the farthest point among our chosen `k` at the root. If we see a new point that is closer than our farthest point, we pop the root and push the new point! This reduces space complexity from O(N) to O(K).
You have exactly 3 VIP passes. You keep the 3 most important people on the list. The least important of those 3 sits at the top of the list so they can easily be crossed out. If a more important person shows up, you kick out the worst VIP and give the pass to the newcomer.
function kClosest(points, k):
maxHeap = []
for p in points:
heappush(maxHeap, (-(p.x^2 + p.y^2), p))
if maxHeap.size > k:
heappop(maxHeap) // pop the farthest point
return maxHeap (extract points)Why do it this way? The problem does not require the output to be strictly sorted, just partitioned! Quick Select is the exact same partition logic used in Quick Sort. We pick a pivot, and move everything smaller than the pivot to the left. If the pivot ends up exactly at index `k`, we know the first `k` elements are our answer. It runs in average O(N) time, the absolute fastest bound for this problem!
A bouncer points at a random person in line (the pivot). He tells everyone who is taller than that person to go to the right line, and everyone shorter to go to the left line. If exactly 5 people are in the left line, he knows he found the 5 shortest people without making them stand in order.
function kClosest(points, k):
l, r = 0, len(points) - 1
while l <= r:
pivot_idx = partition(points, l, r)
if pivot_idx == k:
break
elif pivot_idx < k:
l = pivot_idx + 1
else:
r = pivot_idx - 1
return points[0:k]
Discussion
…