K Closest Points to Origin - Solution & Explanation
Problem Statement
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).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
Example 1:
Input: points = [[1,3],[-2,2]], k = 1 Output: [[-2,2]] Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].
Example 2:
Input: points = [[3,3],[5,-1],[-2,4]], k = 2 Output: [[3,3],[-2,4]] Explanation: The answer [[-2,4],[3,3]] would also be accepted.
Constraints:
1 <= k <= points.length <= 104-104 <= xi, yi <= 104
Approach Overview
Problem Overview: You are given an array of 2D points and an integer k. Each point represents (x, y) on a Cartesian plane. Return the k points closest to the origin (0,0). Distance is measured using Euclidean distance, but you only need the squared distance x*x + y*y for comparisons.
Approach 1: Sort and Select (O(n log n) time, O(1) or O(n) space)
The simplest strategy computes the squared distance for every point and sorts the array by that value. After sorting, the first k points are the closest. Sorting guarantees correct ordering but does more work than required because the entire list is ordered even though you only need the smallest k elements. This approach relies on standard sorting algorithms and is often the easiest implementation across languages.
Approach 2: Max-Heap (Priority Queue) (O(n log k) time, O(k) space)
A more efficient method maintains a max-heap of size k. Iterate through all points, compute the squared distance, and push the point into the heap. If the heap size exceeds k, remove the farthest element (the heap root). The heap always stores the k closest points seen so far. Each insertion or removal costs O(log k), which leads to O(n log k) total time. This method is common in interview problems involving streaming or partial selection and uses a heap (priority queue) to maintain the top candidates efficiently.
Approach 3: Quickselect (Average O(n) time, O(1) extra space)
Quickselect applies the partition logic from quicksort to position the k-th closest distance in the correct place. Choose a pivot, partition the points so those with smaller distances move to the left, and recursively process only the relevant side. Once the pivot index equals k, the first k elements contain the closest points (order does not matter). This technique falls under divide and conquer and avoids fully sorting the array. Average runtime is O(n), though the worst case is O(n^2). In practice it performs very well and is the optimal theoretical solution.
Recommended for interviews: Start with the sorting idea to show clarity, then move to the max-heap solution since it improves complexity to O(n log k) and is widely accepted in interviews. If the interviewer pushes for optimal performance, implement Quickselect for average O(n) time. Demonstrating both heap and selection algorithms shows strong familiarity with partial sorting problems.
Approach 1: Sort and Select
This approach leverages the simplicity of sorting the list of points based on their distance from the origin. After sorting, the first k points will be the closest ones. The key is to use the squared Euclidean distance to avoid the computational overhead of square root operations.
This C code uses the qsort function to sort the points array based on the calculated squared distances. It extracts the first k elements and returns them as the closest points.
Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since the sorting is done in-place.
Approach 2: Max-Heap (Priority Queue)
The Max-Heap approach uses a priority queue to maintain the k closest points seen so far. By using a max-heap, we can efficiently insert new points and potentially evict the farthest point if it is further than any encountered point, leading to a reduced time complexity for finding the k closest points.
This C solution maintains a max-heap of size k using a custom struct. It inserts each point by distance until the max-heap is full. For subsequent points, it compares distances and potentially evicts the farthest point if a closer point is found.
Complexity
Time Complexity: O(n log k) since each insertion/extraction in the heap takes O(log k) time.
Space Complexity: O(k) for the heap storage.
Approach 3: Custom Sorting
We sort all points by their distance from the origin in ascending order, and then take the first k points.
The time complexity is O(n log n), and the space complexity is O(log n). Here, n is the length of the array points.
Approach 4: Priority Queue (Max Heap)
We can use a priority queue (max heap) to maintain the k closest points to the origin.
The time complexity is O(n times log k), and the space complexity is O(k). Here, n is the length of the array points.
Code
Python
Java
C++
Go
TypeScript
Approach 5: Binary Search
We notice that as the distance increases, the number of points increases as well. There exists a critical value such that the number of points before this value is less than or equal to k, and the number of points after this value is greater than k.
Therefore, we can use binary search to enumerate the distance. In each binary search iteration, we count the number of points whose distance is less than or equal to the current distance. If the count is greater than or equal to k, it indicates that the critical value is on the left side, so we set the right boundary equal to the current distance; otherwise, the critical value is on the right side, so we set the left boundary equal to the current distance plus one.
After the binary search is finished, we just need to return the points whose distance is less than or equal to the left boundary.
The time complexity is O(n times log M), and the space complexity is O(n). Here, n is the length of the array points, and M is the maximum value of the distance.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sort and Select | Time Complexity: O(n log n) due to sorting. |
| Max-Heap (Priority Queue) | Time Complexity: O(n log k) since each insertion/extraction in the heap takes O(log k) time. |
| Custom Sorting | — |
| Priority Queue (Max Heap) | — |
| Binary Search | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Select | O(n log n) | O(1)–O(n) | Simple implementation when constraints are small or readability matters more than optimal performance |
| Max-Heap (Priority Queue) | O(n log k) | O(k) | Best practical approach when k is much smaller than n or when processing elements incrementally |
| Quickselect | Average O(n), Worst O(n^2) | O(1) | Optimal selection algorithm when you only need the k smallest elements without full sorting |
Video Solution
K Closest Points to Origin - Heap / Priority Queue - Leetcode 973 - Python • NeetCode • 139,985 views views
Watch 9 more video solutions →Frequently Asked Questions
Is K Closest Points to Origin easy or hard?
How to solve K Closest Points to Origin in O(n)?
What is the best approach for K Closest Points to Origin?
What data structure is used in K Closest Points to Origin?
What is the time complexity of K Closest Points to Origin?
K Closest Points to Origin Python or Java solution approach?
Is K Closest Points to Origin asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice K Closest Points to Origin with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor