K Closest Points to Origin

Heap·Medium

Given an array points where points[i] = [xi, yi] and an integer k, return the k points closest to the origin (0, 0) by Euclidean distance.

The answer must be returned sorted lexicographically as [[x1, y1], [x2, y2], ...] (ascending by x, ties broken by y). This makes the output deterministic when multiple solutions could legitimately disagree on tie-breaking — for example, when several points are equidistant from the origin, a heap-based and a sort-based solution might naturally emit them in different orders.

You may use any approach (max-heap of size k, sort by distance, or quickselect). Just remember to sort the final k points lexicographically before returning.

Examples

Input: points = [[1,3],[-2,2]], k = 1

Output: [[-2,2]]

(-2,2) has distance √8; (1,3) has distance √10. The closer one is (-2,2).

Input: points = [[3,3],[5,-1],[-2,4]], k = 2

Output: [[-2,4],[3,3]]

Distances: √18, √26, √20. Two closest are (3,3) and (-2,4); sorted lexicographically gives [[-2,4],[3,3]].

Constraints

1 <= k <= points.length <= 10^4
-10^4 <= xi, yi <= 10^4

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Sign up free Sign in

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Heap
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.

Sign up to solve this problem