K Closest Points to Origin

Problem in Plain English

Given points on a plane and an integer k, return the k points nearest the origin using Euclidean distance. The answer may come back in any order.

Problem Statement

Given points, where each entry [x,y] is an integer coordinate pair, and k, return the k points with smallest Euclidean distance to the origin [0,0]. Return them in any order.

Compare squared distances $x^2+y^2$ : square root increases with its input, so it cannot change which points are nearer. The statement guarantees a unique selected answer except for output order. These implementations also handle tied cutoff distances by returning any valid k-point selection. They preserve the input and return fresh coordinate arrays.

Constraints

$1 \le k \le n \le 10^4$ , where n is the number of points.
Each coordinate lies between $-10^4$ and $10^4$ , inclusive.
The selected k-point answer is unique except for its output order.

Examples

Example 1

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

The squared distances are 10 and 8, so [-2,2] is closer and is the only point returned.

Example 2

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

The squared distances are 18, 26 and 20, so [3,3] and [-2,4] are the two closest.

Example 3

Input: points = [[0,0],[-1,0],[0,1]], k = 3
Output: [[0,0],[-1,0],[0,1]]

With k equal to n, every point must be returned. The origin has squared distance 0, and the other two points tie at 1. Both tied points are included, so the selected answer remains unique; their relative order is irrelevant.

Example 4

Input: points = [[-2,-2],[-2,-2],[3,0],[0,0]], k = 3
Output: [[0,0],[-2,-2],[-2,-2]]

The distances are 8, 8, 9, and 0. Each duplicate is a separate input occurrence, so both copies of [-2,-2] must be kept with the origin. Keeping only distinct coordinate pairs would wrongly return fewer than three points.

Intuition

The closest points have the smallest squared distances: Example 1 compares 10 for [1,3] with 8 for [-2,2]. Sorting ranks every point. A bounded max-heap only tracks the current k winners; its root is the farthest retained candidate, exactly the one to discard when the candidate set becomes too large. Coordinate signs matter when locating a point, but disappear when measuring distance.

Approaches

Sort by Distance

Solution Details

Reveal Sort by Distance: intuition, complexity, and code

Intuition

Pairing every point with its squared distance reduces the task to sorting pairs and slicing off the first k. The sort is easy to get right but orders every point even though only k of them are needed.

Step-by-Step Logic

Build one distance record per input occurrence using squared coordinates; Example 1 produces [10,1,3] and [8,-2,2].
Sort those records by their first field numerically, producing [8,-2,2] before [10,1,3].
Read exactly the first k records; with k = 1, choose the record at index 0.
Copy its coordinates into a new output row, returning [[-2,2]] in Example 1. The input remains [[1,3],[-2,2]].

Why It Works

Squaring Euclidean distance preserves its order because square root is strictly increasing for nonnegative inputs. After sorting all distance records in ascending order, every record among the first k has distance no greater than every later record. Selecting exactly that prefix therefore gives k nearest points. Each record corresponds to one input occurrence, preserving duplicates. The code builds records instead of sorting the input, and constructs new output coordinate arrays, so input order and ownership are preserved.

Dry Run

Sort by Distance: variable states at each step
operation	records (distance,x,y)	selected count	output
initialize	`[]`	0	`[]`
read index 0: [1,3]	`[[10,1,3]]`	0	`[]`
read index 1: [-2,2]	`[[10,1,3],[8,-2,2]]`	0	`[]`
sort records	`[[8,-2,2],[10,1,3]]`	0	`[]`
copy first k = 1	`[[8,-2,2],[10,1,3]]`	1	`[[-2,2]]`

Complexity Analysis

Time Complexity

O(n log n)

Space Complexity

O(n)

For n points, building distance records takes O(n), sorting takes O(n log n), and copying the answer takes O(k). Records occupy O(n), output owns O(k) fresh coordinate rows, and conventional sorting may use O(n) scratch storage. Python and JavaScript also allocate an O(k) slice before mapping; all of this is O(n) total since k <= n. The input itself is never copied wholesale or reordered.

Code

Solution.java

1import java.util.ArrayList;2import java.util.Comparator;3import java.util.List;4
5class Solution {6    public int[][] kClosest(int[][] points, int k) {7        List<int[]> pairs = new ArrayList<>();8        for (int[] p : points) {9            // At the stated bounds, squared distance is at most 200,000,000: int is safe.10            pairs.add(new int[]{p[0] * p[0] + p[1] * p[1], p[0], p[1]});11        }12        pairs.sort(Comparator.comparingInt(a -> a[0]));13        int[][] res = new int[k][2];14        for (int i = 0; i < k; i++) {15            // Fill owned output rows; never return references into the input.16            res[i][0] = pairs.get(i)[1];17            res[i][1] = pairs.get(i)[2];18        }19        return res;20    }21}

Hints

Hint 1

Compare x*x + y*y instead of the true Euclidean distance to stay in exact integer arithmetic.

Hint 2

Sorting all distances works, but only k winners are needed, so most of that ordering is wasted.

Hint 3

Hold k candidates in a max-heap and evict the top whenever a closer point arrives.

Edge Cases

For k = 1, the heap has at most two entries during insertion and the whole scan remains linear.
For k = n, all occurrences are returned, with no requirement to sort the output.
The origin has squared distance zero and outranks every non-origin point.
Negative coordinates and duplicates require no special branch; retain multiplicity rather than using a set.
Equal distances among selected points are valid. Ties exactly at the cutoff are outside the unique-answer guarantee, but this code still returns any valid k survivors.
Maximum coordinate magnitudes yield squared distance 200,000,000, safely inside Java int and JavaScript exact integer range.

Common Mistakes and Interview Tips

Using a min-heap while evicting the root: that removes the closest point instead of the farthest.
Checking capacity before insertion without a correct replacement rule; push then evict makes the candidate invariant explicit.
Discarding duplicate coordinates in a set, which loses input occurrences.
Requiring ascending output order even though heap order is accepted.
Returning heap row references directly in Java or JavaScript, which lets output mutation alter the caller's input.
Claiming O(n log k) literally for k = 1, where log 1 is zero; O(n log(k+1)) covers the mandatory scan.

Key Takeaway

For the k smallest of anything, cap a max-heap at k entries and let each arrival evict the current worst survivor.