Practice › Heap & Priority Queue
K Closest Points to Origin
Medium · Heap & Priority Queue · Asked at Amazon, Meta, Google, Uber, LinkedIn
Print the k points closest to the origin (0, 0) by Euclidean distance. Order the output by distance; break ties by smaller x, then smaller y.
Input
First line: n k. Next n lines: x y.
Output
k lines, each x y.
Constraints
- 1 ≤ k ≤ n ≤ 10^4
- -10^4 ≤ x, y ≤ 10^4
Compare squared distances (no square roots, no floating point). A max-heap of size k keeps the k best seen so far; sort them at the end.
Example 1
Input
2 1 1 3 -2 2
Output
-2 2
Example 2
Input
3 2 3 3 5 -1 -2 4
Output
3 3 -2 4
Hints
- Compare x² + y² — no square root needed, and it stays an exact integer.
- Keep a max-heap of size k ordered by (distance, x, y); a point better than the heap top replaces it. Sort the k survivors at the end.
Approach
Order points by the key (x² + y², x, y). A max-heap of size k holds the k best keys seen so far: push each point and pop the largest when the size exceeds k. Finally sort the remaining k points by the same key and print them. (With n ≤ 10^4 a full sort is also fine; the heap version is what interviewers expect for large n.)
Complexity: O(n log k) time · O(k) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
priority_queue<tuple<long long, long long, long long>> pq; // max-heap on (dist, x, y)
for (int i = 0; i < n; i++) {
long long x, y;
cin >> x >> y;
pq.emplace(x * x + y * y, x, y);
if ((int)pq.size() > k) pq.pop();
}
vector<tuple<long long, long long, long long>> v;
while (!pq.empty()) v.push_back(pq.top()), pq.pop();
sort(v.begin(), v.end());
for (auto &t : v) cout << get<1>(t) << " " << get<2>(t) << "\n";
return 0;
}Python solution
import sys
import heapq
data = list(map(int, sys.stdin.read().split()))
n, k = data[0], data[1]
heap = [] # max-heap via negated keys
for i in range(n):
x, y = data[2 + 2 * i], data[3 + 2 * i]
heapq.heappush(heap, (-(x * x + y * y), -x, -y))
if len(heap) > k:
heapq.heappop(heap)
pts = sorted((-d, -x, -y) for d, x, y in heap)
print("\n".join(f"{x} {y}" for _, x, y in pts))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
Comparator<long[]> byKey = (p, q) -> p[0] != q[0] ? Long.compare(p[0], q[0]) : p[1] != q[1] ? Long.compare(p[1], q[1]) : Long.compare(p[2], q[2]);
PriorityQueue<long[]> pq = new PriorityQueue<>(byKey.reversed());
for (int i = 0; i < n; i++) {
long x = sc.nextLong(), y = sc.nextLong();
pq.add(new long[] {x * x + y * y, x, y});
if (pq.size() > k) pq.poll();
}
List<long[]> v = new ArrayList<>(pq);
v.sort(byKey);
StringBuilder sb = new StringBuilder();
for (long[] p : v) sb.append(p[1]).append(' ').append(p[2]).append('\n');
System.out.print(sb);
}
}Solve K Closest Points to Origin online · All practice problems