K Closest Points to Origin

Medium · Heap / Priority Queue

You are given a list of points on a 2D plane, each described by its x and y coordinates, and an integer k. Return the k points that are nearest to the origin (0, 0), measured by straight-line distance. You may return the k points in any order.

Examples

Input:  points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Why:    Distance of (-2,2) is sqrt(8) which is smaller than sqrt(10) for (1,3), so it is the closest single point.

Input:  points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Why:    Distances are sqrt(18), sqrt(26), sqrt(20); the two smallest belong to (3,3) and (-2,4).

Input:  points = [[0,0],[1,1],[2,2]], k = 2
Output: [[0,0],[1,1]]
Why:    The origin itself has distance 0, and (1,1) is the next closest.

Constraints

1 <= k <= points.length <= 10^4, -10^4 <= points[i][0], points[i][1] <= 10^4

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise K Closest Points to Origin

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of K Closest Points to Origin. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.