Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Compare x² + y² — no square root needed, and it stays an exact integer.
  2. 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