973. K Closest Points to Origin - Explanation

Description

You are given an 2-D array points where points[i] = [xi, yi] represents the coordinates of a point on an X-Y axis plane. You are also given an integer k.

Return the k closest points to the origin (0, 0).

The distance between two points is defined as the Euclidean distance (sqrt((x1 - x2)^2 + (y1 - y2)^2)).

You may return the answer in any order.

Example 1:

Input: points = [[0,2],[2,2]], k = 1

Output: [[0,2]]

Explanation : The distance between (0, 2) and the origin (0, 0) is 2. The distance between (2, 2) and the origin is sqrt(2^2 + 2^2) = 2.82842. So the closest point to the origin is (0, 2).

Example 2:

Input: points = [[0,2],[2,0],[2,2]], k = 2

Output: [[0,2],[2,0]]

Explanation: The output [2,0],[0,2] would also be accepted.

Constraints:

1 <= k <= points.length <= 1000
-100 <= points[i][0], points[i][1] <= 100

Topics

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(nlogk) time and O(k) space, where n is the size of the input array, and k is the number of points to be returned.

Hint 1

A naive solution would be to sort the array in ascending order based on the distances of the points from the origin (0, 0) and return the first k points. This would take O(nlogn) time. Can you think of a better way? Perhaps you could use a data structure that maintains only k points and allows efficient insertion and removal.

Hint 2

We can use a Max-Heap that keeps the maximum element at its top and allows retrieval in O(1) time. This data structure is ideal because we need to return the k closest points to the origin. By maintaining only k points in the heap, we can efficiently remove the farthest point when the size exceeds k. How would you implement this?

Hint 3

We initialize a Max-Heap that orders points based on their distances from the origin. Starting with an empty heap, we iterate through the array of points, inserting each point into the heap. If the size of the heap exceeds k, we remove the farthest point (the maximum element in the heap). After completing the iteration, the heap will contain the k closest points to the origin. Finally, we convert the heap into an array and return it.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sorting with Custom Comparators - Sorting elements based on a computed value (distance) rather than the elements themselves
Euclidean Distance - Understanding that distance from origin is sqrt(x^2 + y^2), and that squared distance preserves ordering
Heap Data Structure - Using min-heaps and max-heaps to efficiently track smallest/largest elements
QuickSelect Algorithm - Partitioning arrays to find the k-th element in average O(n) time without full sorting

1. Sorting

Intuition

To find the k closest points to the origin (0, 0), we compare points by their distance from the origin.
Since the actual distance uses a square root, and square root preserves ordering, we can instead compare using squared distance:

[
d^2 = x^2 + y^2
]

This avoids unnecessary computation and is sufficient for sorting.

If we sort all points by this squared distance, then the first k points in sorted order must be the k closest ones.

Algorithm

For every point (x, y), compute its squared distance: dist = x^2 + y^2
Sort all points based on this dist value.
Return the first k points from the sorted list.

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        points.sort(key=lambda p: p[0]**2 + p[1]**2)
        return points[:k]

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        sort(points.begin(), points.end(), [](const auto& a, const auto& b) {
            return (a[0] * a[0] + a[1] * a[1]) < (b[0] * b[0] + b[1] * b[1]);
        });
        return vector<vector<int>>(points.begin(), points.begin() + k);
    }
};

class Solution {
    /**
     * @param {number[][]} points
     * @param {number} k
     * @return {number[][]}
     */
    kClosest(points, k) {
        points.sort((a, b) => a[0] ** 2 + a[1] ** 2 - (b[0] ** 2 + b[1] ** 2));
        return points.slice(0, k);
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

2. Min-Heap

Intuition

A min-heap always gives you the smallest element first.
If we insert every point into a min-heap, using its squared distance from the origin as the priority, then:

The closest point will be at the top.
The next closest will be removed next, and so on.

So if we remove from the heap k times, we get exactly the k closest points.

This works because the heap always keeps the smallest distances at the front.

Algorithm

Create an empty min-heap.
For each point (x, y):
- Compute squared distance x^2 + y^2.
- Push (distance, x, y) into the heap.
Repeat k times:
- Remove the smallest element from the heap.
- Add its (x, y) coordinates to the result.
Return the result list of k closest points.

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        minHeap = []
        for x, y in points:
            dist = (x ** 2) + (y ** 2)
            minHeap.append([dist, x, y])

        heapq.heapify(minHeap)
        res = []
        while k > 0:
            dist, x, y = heapq.heappop(minHeap)
            res.append([x, y])
            k -= 1

        return res

public class Solution {
    public int[][] kClosest(int[][] points, int K) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparing(a -> a[0]));
        for (int[] point : points) {
            int dist = point[0] * point[0] + point[1] * point[1];
            minHeap.offer(new int[]{dist, point[0], point[1]});
        }

        int[][] result = new int[K][2];
        for (int i = 0; i < K; ++i) {
            int[] point = minHeap.poll();
            result[i] = new int[]{point[1], point[2]};
        }
        return result;
    }
}

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        auto comp = [](const vector<int>& a, const vector<int>& b) {
            return a[0]*a[0] + a[1]*a[1] > b[0]*b[0] + b[1]*b[1];
        };

        priority_queue<vector<int>, vector<vector<int>>, decltype(comp)> minHeap(comp);

        for (const auto& point : points) {
            minHeap.push({point[0], point[1]});
        }

        vector<vector<int>> result;
        for (int i = 0; i < K; ++i) {
            result.push_back(minHeap.top());
            minHeap.pop();
        }
        return result;
    }
};

/**
 * const { MinPriorityQueue } = require('@datastructures-js/priority-queue');
 */

class Solution {
    /**
     * @param {number[][]} points
     * @param {number} k
     * @return {number[][]}
     */
    kClosest(points, k) {
        const minHeap = new MinPriorityQueue((point) => point[0]);

        for (const [x, y] of points) {
            const dist = x ** 2 + y ** 2;
            minHeap.enqueue([dist, x, y]);
        }

        const res = [];
        for (let i = 0; i < k; i++) {
            const [_, x, y] = minHeap.dequeue();
            res.push([x, y]);
        }

        return res;
    }
}

public class Solution {
    public int[][] KClosest(int[][] points, int K) {
        PriorityQueue<int[], int> minHeap = new PriorityQueue<int[], int>();
        foreach (int[] point in points) {
            int dist = point[0] * point[0] + point[1] * point[1];
            minHeap.Enqueue(new int[] { dist, point[0], point[1] }, dist);
        }

        int[][] result = new int[K][];
        for (int i = 0; i < K; ++i) {
            int[] point = minHeap.Dequeue();
            result[i] = new int[] { point[1], point[2] };
        }
        return result;
    }
}

func kClosest(points [][]int, k int) [][]int {
    minHeap := priorityqueue.NewWith(func(a, b interface{}) int {
        distA := a.([]int)[0]
        distB := b.([]int)[0]
        return distA - distB
    })

    for _, point := range points {
        x, y := point[0], point[1]
        dist := x*x + y*y
        minHeap.Enqueue([]int{dist, x, y})
    }

    res := [][]int{}
    for i := 0; i < k; i++ {
        item, _ := minHeap.Dequeue()
        point := item.([]int)
        res = append(res, []int{point[1], point[2]})
    }

    return res
}

class Solution {
    fun kClosest(points: Array<IntArray>, k: Int): List<IntArray> {
        val minHeap = PriorityQueue(compareBy<IntArray> { it[0] * it[0] + it[1] * it[1] })

        for (point in points) {
            minHeap.add(point)
        }

        val res = mutableListOf<IntArray>()
        repeat(k) {
            res.add(minHeap.poll())
        }

        return res
    }
}

struct Item: Comparable {
    let dist: Int
    let x: Int
    let y: Int

    static func < (lhs: Item, rhs: Item) -> Bool {
        return lhs.dist < rhs.dist
    }
}

class Solution {
    func kClosest(_ points: [[Int]], _ k: Int) -> [[Int]] {
        var minHeap = Heap<Item>()

        for point in points {
            let x = point[0], y = point[1]
            let dist = x * x + y * y
            minHeap.insert(Item(dist: dist, x: x, y: y))
        }

        var res = [[Int]]()
        for _ in 0..<k {
            if let item = minHeap.popMin() {
                res.append([item.x, item.y])
            }
        }

        return res
    }
}

Time & Space Complexity

Time complexity: $O(n + k * \log n)$
Space complexity: $O(n)$

Where $n$ is the length of the array $points$ .

3. Max Heap

Intuition

We want the k closest points, not all points sorted.

Use a max-heap of size k:

The heap always keeps the k closest points found so far.
The point with the largest distance among these k sits at the top.
When a new point is closer than the farthest in the heap, we remove the farthest and insert the new one.

This way, the heap never grows beyond size k, and it always contains the k best candidates.

Algorithm

Create an empty max-heap.
For each point:
- Compute its squared distance from origin: d = x^2 + y^2.
- Insert (d, point) into the heap.
- If heap size exceeds k:
  - Remove the element with the maximum distance.
After processing all points:
- The heap contains exactly the k closest points.
Return all points stored in the heap.

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        maxHeap = []
        for x, y in points:
            dist = -(x ** 2 + y ** 2)
            heapq.heappush(maxHeap, [dist, x, y])
            if len(maxHeap) > k:
                heapq.heappop(maxHeap)

        res = []
        while maxHeap:
            dist, x, y = heapq.heappop(maxHeap)
            res.append([x, y])
        return res

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        priority_queue<pair<int, pair<int, int>>> maxHeap;
        for (auto& point : points) {
            int dist = point[0] * point[0] + point[1] * point[1];
            maxHeap.push({dist, {point[0], point[1]}});
            if (maxHeap.size() > k) {
                maxHeap.pop();
            }
        }

        vector<vector<int>> res;
        while (!maxHeap.empty()) {
            res.push_back({maxHeap.top().second.first,
                           maxHeap.top().second.second});
            maxHeap.pop();
        }
        return res;
    }
};

/**
 * const { PriorityQueue } = require('@datastructures-js/priority-queue');
 */

class Solution {
    /**
     * @param {number[][]} points
     * @param {number} k
     * @return {number[][]}
     */
    kClosest(points, k) {
        const maxHeap = new PriorityQueue((a, b) => b[0] - a[0]);

        for (const [x, y] of points) {
            const dist = x ** 2 + y ** 2;
            maxHeap.push([dist, x, y]);
            if (maxHeap.size() > k) {
                maxHeap.pop();
            }
        }

        const res = [];
        while (maxHeap.size() > 0) {
            let tmp = maxHeap.pop();
            res.push([tmp[1], tmp[2]]);
        }
        return res;
    }
}

public class Solution {
    public int[][] KClosest(int[][] points, int K) {
        PriorityQueue<int[], int> maxHeap = new();

        foreach (var point in points) {
            int dist = point[0] * point[0] + point[1] * point[1];
            maxHeap.Enqueue(point, -dist);
            if (maxHeap.Count > K) {
                maxHeap.Dequeue();
            }
        }

        var res = new List<int[]>();
        while (maxHeap.Count > 0) {
            res.Add(maxHeap.Dequeue());
        }

        return res.ToArray();
    }
}

func kClosest(points [][]int, k int) [][]int {
    maxHeap := priorityqueue.NewWith(func(a, b interface{}) int {
        distA := a.([]int)[2]
        distB := b.([]int)[2]
        if distA > distB {
            return -1
        } else if distA < distB {
            return 1
        }
        return 0
    })

    for _, point := range points {
        x, y := point[0], point[1]
        dist := x*x + y*y
        maxHeap.Enqueue([]int{x, y, dist})
        if maxHeap.Size() > k {
            maxHeap.Dequeue()
        }
    }

    result := make([][]int, k)
    for i := k - 1; i >= 0; i-- {
        val, _ := maxHeap.Dequeue()
        point := val.([]int)
        result[i] = []int{point[0], point[1]}
    }

    return result
}

struct Item: Comparable {
    let dist: Int
    let x: Int
    let y: Int

    static func < (lhs: Item, rhs: Item) -> Bool {
        return lhs.dist > rhs.dist
    }
}

class Solution {
    func kClosest(_ points: [[Int]], _ k: Int) -> [[Int]] {
        var maxHeap = Heap<Item>()

        for point in points {
            let x = point[0], y = point[1]
            let dist = x * x + y * y
            maxHeap.insert(Item(dist: dist, x: x, y: y))
            if maxHeap.count > k {
                _ = maxHeap.popMin()
            }
        }

        var res = [[Int]]()
        while !maxHeap.isEmpty {
            if let item = maxHeap.popMin() {
                res.append([item.x, item.y])
            }
        }

        return res
    }
}

Time & Space Complexity

Time complexity: $O(n * \log k)$
Space complexity: $O(k)$

Where $n$ is the length of the array $points$ .

4. Quick Select

Intuition

We want the k closest points, but we do NOT need them sorted.

This is a perfect use-case for QuickSelect, the same idea used in QuickSort's partition step:

Pick a pivot point.
Partition all points into:
- points closer than the pivot
- points farther than the pivot
After partitioning, the pivot ends at its correct position in the final sorted order.
If the pivot ends up at index p:
- If p == k, then the left side already contains the k closest points.
- If p < k, search the right half.
- If p > k, search the left half.

This avoids fully sorting the array and runs in average O(N) time.

Algorithm

Define a function to compute squared distance: dist = x^2 + y^2.
Use a partition function:
- Choose a pivot distance.
- Rearrange points so all smaller distances go left, larger go right.
- Return the pivot's final index.
Maintain two pointers: L = 0, R = n - 1.
Repeatedly partition:
- If pivot index p == k, stop.
- If p < k, move L = p + 1.
- If p > k, move R = p - 1.
After partitioning ends, the first k points in the array are the k closest.
Return those k points.

class Solution:
    def kClosest(self, points, k):
        euclidean = lambda x: x[0] ** 2 + x[1] ** 2
        def partition(l, r):
            pivotIdx = r
            pivotDist = euclidean(points[pivotIdx])
            i = l
            for j in range(l, r):
                if euclidean(points[j]) <= pivotDist:
                    points[i], points[j] = points[j], points[i]
                    i += 1
            points[i], points[r] = points[r], points[i]
            return i

        L, R = 0, len(points) - 1
        pivot = len(points)

        while pivot != k:
            pivot = partition(L, R)
            if pivot < k:
                L = pivot + 1
            else:
                R = pivot - 1
        return points[:k]

public class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int L = 0, R = points.length - 1;
        int pivot = points.length;

        while (pivot != k) {
            pivot = partition(points, L, R);
            if (pivot < k) {
                L = pivot + 1;
            } else {
                R = pivot - 1;
            }
        }
        int[][] res = new int[k][2];
        System.arraycopy(points, 0, res, 0, k);
        return res;
    }

    private int partition(int[][] points, int l, int r) {
        int pivotIdx = r;
        int pivotDist = euclidean(points[pivotIdx]);
        int i = l;
        for (int j = l; j < r; j++) {
            if (euclidean(points[j]) <= pivotDist) {
                int[] temp = points[i];
                points[i] = points[j];
                points[j] = temp;
                i++;
            }
        }
        int[] temp = points[i];
        points[i] = points[r];
        points[r] = temp;
        return i;
    }

    private int euclidean(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }
}

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        int L = 0, R = points.size() - 1;
        int pivot = points.size();

        while (pivot != k) {
            pivot = partition(points, L, R);
            if (pivot < k) {
                L = pivot + 1;
            } else {
                R = pivot - 1;
            }
        }
        return vector<std::vector<int>>(points.begin(), points.begin() + k);
    }

private:
    int partition(vector<vector<int>>& points, int l, int r) {
        int pivotIdx = r;
        int pivotDist = euclidean(points[pivotIdx]);
        int i = l;
        for (int j = l; j < r; j++) {
            if (euclidean(points[j]) <= pivotDist) {
                swap(points[i], points[j]);
                i++;
            }
        }
        swap(points[i], points[r]);
        return i;
    }

    int euclidean(vector<int>& point) {
        return point[0] * point[0] + point[1] * point[1];
    }
};

class Solution {
    /**
     * @param {number[][]} points
     * @param {number} k
     * @return {number[][]}
     */
    kClosest(points, k) {
        let L = 0,
            R = points.length - 1,
            pivot = points.length;

        while (pivot !== k) {
            pivot = this.partition(points, L, R);
            if (pivot < k) {
                L = pivot + 1;
            } else {
                R = pivot - 1;
            }
        }
        return points.slice(0, k);
    }

    /**
     * @param {number[][]} points
     * @param {number} l
     * @param {number} r
     * @return {number}
     */
    partition(points, l, r) {
        const pivotIdx = r;
        const pivotDist = this.euclidean(points[pivotIdx]);
        let i = l;
        for (let j = l; j < r; j++) {
            if (this.euclidean(points[j]) <= pivotDist) {
                [points[i], points[j]] = [points[j], points[i]];
                i++;
            }
        }
        [points[i], points[r]] = [points[r], points[i]];
        return i;
    }

    /**
     * @param {number[]} point
     * @return {number}
     */
    euclidean(point) {
        return point[0] ** 2 + point[1] ** 2;
    }
}

class Solution {
    public int[][] KClosest(int[][] points, int k) {
        int L = 0, R = points.Length - 1;
        int pivot = points.Length;

        while (pivot != k) {
            pivot = Partition(points, L, R);
            if (pivot < k) {
                L = pivot + 1;
            } else {
                R = pivot - 1;
            }
        }
        int[][] res = new int[k][];
        Array.Copy(points, res, k);
        return res;
    }

    private int Partition(int[][] points, int l, int r) {
        int pivotIdx = r;
        int pivotDist = Euclidean(points[pivotIdx]);
        int i = l;
        for (int j = l; j < r; j++) {
            if (Euclidean(points[j]) <= pivotDist) {
                Swap(points, i, j);
                i++;
            }
        }
        Swap(points, i, r);
        return i;
    }

    private int Euclidean(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }

    private void Swap(int[][] points, int i, int j) {
        int[] temp = points[i];
        points[i] = points[j];
        points[j] = temp;
    }
}

class Solution {
    fun kClosest(points: Array<IntArray>, k: Int): Array<IntArray> {
        val euclidean = { x: IntArray -> x[0] * x[0] + x[1] * x[1] }

        fun partition(points: Array<IntArray>, l: Int, r: Int): Int {
            val pivotIdx = r
            val pivotDist = euclidean(points[pivotIdx])
            var i = l
            for (j in l until r) {
                if (euclidean(points[j]) <= pivotDist) {
                    points[i] = points[j].also { points[j] = points[i] }
                    i++
                }
            }
            points[i] = points[r].also { points[r] = points[i] }
            return i
        }

        var L = 0
        var R = points.size - 1
        var pivot = points.size

        while (pivot != k) {
            pivot = partition(points, L, R)
            if (pivot < k) {
                L = pivot + 1
            } else {
                R = pivot - 1
            }
        }
        return points.copyOfRange(0, k)
    }
}

class Solution {
    func kClosest(_ points: [[Int]], _ k: Int) -> [[Int]] {
        var points = points

        func euclidean(_ point: [Int]) -> Int {
            return point[0] * point[0] + point[1] * point[1]
        }

        func partition(_ l: Int, _ r: Int) -> Int {
            let pivotIdx = r
            let pivotDist = euclidean(points[pivotIdx])
            var i = l
            for j in l..<r {
                if euclidean(points[j]) <= pivotDist {
                    points.swapAt(i, j)
                    i += 1
                }
            }
            points.swapAt(i, r)
            return i
        }

        var l = 0, r = points.count - 1
        var pivot = points.count

        while pivot != k {
            pivot = partition(l, r)
            if pivot < k {
                l = pivot + 1
            } else {
                r = pivot - 1
            }
        }

        return Array(points[..<k])
    }
}

Time & Space Complexity

Time complexity: $O(n)$ in average case, $O(n ^ 2)$ in worst case.
Space complexity: $O(1)$

Common Pitfalls

Computing Actual Distance with Square Root

Using sqrt(x^2 + y^2) is unnecessary and introduces floating-point precision issues. Since we only compare relative distances, squared distance x^2 + y^2 preserves ordering and avoids costly square root operations.

Using the Wrong Heap Type

For the heap approach, using a min-heap requires extracting k elements at the end, while a max-heap of size k naturally keeps the k closest. Mixing these up leads to incorrect results or inefficient solutions that maintain more elements than needed.

Integer Overflow in Distance Calculation

When coordinates can be large (up to 10^4), squaring them produces values up to 10^8. While this fits in a 32-bit integer, summing two such values approaches the limit. In languages with overflow concerns, ensure your distance calculation uses appropriate integer types.