Closest Points to Origin | Dataford Interview Questions

K Closest Points to Origin

Asked in the Pair Programming stage of the QuantumBlack GenAI-heavy Data Scientist pair programming round. Reported follow-ups included general space and time complexity questions.

Given points, where each point is [x, y], and integer k, return the k points closest to [0, 0]. Use squared Euclidean distance, x² + y², and return points in ascending distance order, breaking ties by original input order.

Examples: points = [[1,3],[-2,2]], k = 1 returns [[-2,2]]. points = [[3,3],[5,-1],[-2,4]], k = 2 returns [[3,3],[-2,4]].

Constraints: 1 <= k <= len(points) <= 10^4; coordinates are between -10^4 and 10^4.

Constraints

1 <= k <= len(points) <= 10^4
points[i] contains exactly two integers
-10^4 <= points[i][0], points[i][1] <= 10^4
Return exactly k points

Function Signature

def k_closest(points, k):

Your question is Closest Points to Origin. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem