K Closest Points to Origin

MediumHeapheap / quickselect

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a list of points on a 2D plane, where each entry points[i] = [x, y] represents the coordinates of a single point. You are also given an integer k. Return the k points that are **closest** to the origin (0, 0). Distance between two points is measured using the standard **Euclidean distance**: the distance from (x, y) to the origin is sqrt(x*x + y*y). Note that to compare distances you do not actually need the square root, since comparing the squared distances x*x + y*y preserves the same ordering. The answer may be returned in **any order**, and it is guaranteed to be **unique** except for the order of the returned points (no two points are equidistant in a way that would cause ambiguity about which k to pick). Each returned point should be a two-element list [x, y] taken directly from the input.

Examples

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
The squared distance of [1,3] is 1+9=10, and of [-2,2] is 4+4=8. Since 8 < 10, [-2,2] is the single closest point.
Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Squared distances are 18, 26, and 20. The two smallest belong to [3,3] (18) and [-2,4] (20). The order of the returned pair does not matter.
Input: points = [[0,0],[1,1],[2,2],[3,3]], k = 3
Output: [[0,0],[1,1],[2,2]]
Squared distances are 0, 2, 8, 18. The three nearest to the origin are the first three points.

Constraints

  • `1 <= k <= points.length <= 10^4`
  • `-10^4 <= xi, yi <= 10^4`
  • Each `points[i]` has exactly two integer coordinates `[xi, yi]`.
  • The set of `k` closest points is unique; only their order may vary.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.