MediumNo. 0973

K Closest Points to Origin — LeetCode 973 Python Solution

Topics
Geometry, Array, Math, Divide and Conquer, Quickselect, Sorting, Heap (Priority Queue)
On study lists
NeetCode 150 and Grind 75
Reading time
2 min

The problem

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0). The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

Example

Input
points = [[1,3],[-2,2]], k = 1
Output
[[-2,2]]
Explanation
The distance between (1, 3) and the origin is sqrt(10).

Python solution

PythonSolution
class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        points.sort(key=lambda p: hypot(p[0], p[1]))
        return points[:k]

Complexity

Time
O(n log n)
Space · auxiliary
O(log n)

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 973. K Closest Points to Origin is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 973. K Closest Points to Origin?

LeetCode 973. K Closest Points to Origin is rated Medium on LeetCode.

What is the time complexity of LeetCode 973. K Closest Points to Origin?

The Python solution on this page runs in O(n log n).

What is the space complexity of LeetCode 973. K Closest Points to Origin?

The Python solution on this page uses O(log n) auxiliary space.

What topics does LeetCode 973. K Closest Points to Origin cover?

LeetCode 973. K Closest Points to Origin is tagged Geometry, Array, Math, Divide and Conquer, Quickselect, Sorting and Heap (Priority Queue) on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.