Problem statement

Given an array of points where points[i] = [x, y] and an integer k, return the k points closest to the origin (0, 0).

Distance is the usual Euclidean distance. Return the points sorted by distance ascending, breaking ties by x and then by y, both ascending.

Example 1

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation: √8 < √10.

Example 2

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

Example 3

Input: points = [[0,1],[1,0]], k = 2
Output: [[0,1],[1,0]]
Explanation: Equal distances, so x then y decides.

Constraints

• 1 <= k <= points.length <= 30
• -100 <= x, y <= 100

Hints for K Closest Points to Origin

1. Hint 1

   Compare squared distances — the square root is monotone and only costs precision.

2. Hint 2

   Sorting is O(n log n); a max-heap of size k or quickselect does better on large inputs.

3. Hint 3

   The tie-break is part of the specification here, so it must be applied even when distances are equal.

How to solve K Closest Points to Origin

Sort by squared distance with the specified (x, y) tie-break and take the first k.

Approach

1. Sort points by (x² + y², x, y).
2. Return the first k.

Why it works

Squared distance is monotone in distance, so it orders identically without square roots or floating point; the tie-break is part of the specification.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• A max-heap of size k or quickselect improves large inputs, but the tie-break must still be applied.

Reference solution

Python

def kClosest(points, k: int):
    ordered = sorted(points, key=lambda p: (p[0] * p[0] + p[1] * p[1], p[0], p[1]))
    return ordered[:k]

Java

public static int[][] kClosest(int[][] points, int k) {
    int[][] s = points.clone();
    Arrays.sort(s, (a, b) -> {
        int da = a[0] * a[0] + a[1] * a[1];
        int db = b[0] * b[0] + b[1] * b[1];
        if (da != db) return da - db;
        if (a[0] != b[0]) return a[0] - b[0];
        return a[1] - b[1];
    });
    return Arrays.copyOfRange(s, 0, k);
}

C++

vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    vector<vector<int>> s = points;
    sort(s.begin(), s.end(), [](const vector<int>& a, const vector<int>& b) {
        int da = a[0] * a[0] + a[1] * a[1];
        int db = b[0] * b[0] + b[1] * b[1];
        if (da != db) return da < db;
        if (a[0] != b[0]) return a[0] < b[0];
        return a[1] < b[1];
    });
    s.resize(k);
    return s;
}

JavaScript

var kClosest = function(points, k) {
    const sorted = points.slice().sort(function(a, b) {
        const da = a[0] * a[0] + a[1] * a[1];
        const db = b[0] * b[0] + b[1] * b[1];
        if (da !== db) return da - db;
        if (a[0] !== b[0]) return a[0] - b[0];
        return a[1] - b[1];
    });
    return sorted.slice(0, k);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium