Find the K closest points to the origin.
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3], [-2,4]]
Explanation: The squared distances are 18, 26, and 20 respectively. The two smallest distances belong to [3,3] and [-2,4].

Question

Find the K closest points to the origin.

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

Input: points = [[3,3],[5,-1],[-2,4]], k = 2

Output: [[3,3], [-2,4]]

Explanation: The squared distances are 18, 26, and 20 respectively. The two smallest distances belong to [3,3] and [-2,4].

Anonymous · Accepted Answer

def k_closest(points, k):

distances = []

# Step 1: compute the distance of each point

for point in points:

x = point[0]

y = point[1]

d = x x + y y

distances.append((d, point))

# Step 2: sort by distance (smallest first)

distances.sort()

# Step 3: take the first k points

result = []

for i in range(k):

result.append(distances[i][1])

return result

Anonymous · Answer

public int[][] kClosest(int[][] points, int k) { PriorityQueue queue = new PriorityQueue<>( (a1, a2) -> (a1[0] a1[0] + a1[1] a1[1]) - (a2[0] a2[0] + a2[1] a2[1])); for (int[] point : points) { queue.offer(point); } int[][] ans = new int[k][2]; for (int i = 0; i < k; i++) { ans[i] = queue.poll(); } return ans; }

Find the K closest points to the origin.

Practice this question with AI

Go Premium

Community Answers

Unlock Full Access

Unlock Full Access

Practice More Questions