MediumNo. 0973
K Closest Points to Origin — LeetCode 973 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Geometry, Array, Math, Divide and Conquer, Quickselect, Sorting, Heap (Priority Queue)
- On study lists
- NeetCode 150 and Grind 75
- Reading time
- 2 min
- Source
- leetcode.com
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
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
| No. | Problem | Difficulty |
|---|---|---|
| 0215 | Kth Largest Element in an Array | Medium |
| 1738 | Find Kth Largest XOR Coordinate Value | Medium |
| 1985 | Find the Kth Largest Integer in the Array | Medium |
| 2343 | Query Kth Smallest Trimmed Number | Medium |
| 0218 | The Skyline Problem | Hard |
| 0912 | Sort an Array | Medium |
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.