Skip to main content

K Closest Points to Origin

Question​

Given an array of points in a two-dimensional plane and a positive integer K, find the K closest points to the origin (0, 0).

Example 1
None

Solution​

all//K Closest Points to Origin.py


import math

def kClosestPointsToOrigin(points, k):

    # store distance and point in a hashmap
    dist_map = {}
    for point in points:
        x, y = point
        dist = math.sqrt(x*x + y*y)
        dist_map[point] = dist

    # sort the map based on distance
    sorted_points = sorted(dist_map.items(), key=lambda x: x[1])

    # return the k closest points
    return [sorted_points[i][0] for i in range(k)]

# test
points = [(1, 3), (3, 4), (2, -1)]
k = 2

print(kClosestPointsToOrigin(points, k)) # [(1, 3), (2, -1)]