#0064

K Closest Points to Origin

MediumDSA25 min20 XP

Problem

Given points as [x, y] pairs and integer k, return any k points closest to (0, 0). Compare using squared distance x*x + y*y.

Why This Matters

Priority queues solve top-k problems without sorting everything when only the best few items matter.

Function Signature

def k_closest(points, k):

Examples

Example 1

Inputpoints = [[1,3],[-2,2],[4,4]], k = 2

Output[[-2,2],[1,3]] in any order

Distances are 10, 8, and 32, so the first two points are closest.

Constraints

k may be larger than the number of points.
Output order does not matter.
Use squared distance; no square root is needed.

CodePython

def k_closest(points, k):
    """
    Input example: points = [[1,3],[-2,2],[4,4]], k = 2
    Return: [[-2,2],[1,3]] in any order
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return []

def k_closest(points, k):
    """
    Input example: points = [[1,3],[-2,2],[4,4]], k = 2
    Return: [[-2,2],[1,3]] in any order
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return []

Visible browser tests run here when available.

Testcases1 visible / 3 hidden categories

Two closest points

Input[[1,3],[-2,2],[4,4]], 2

Expected[[-2,2],[1,3]]

The farthest point [4,4] should be excluded.

Hidden Test Categories

k equals zeronegative coordinatesk larger than list length