What is the brute force approach and complexity for K Closest Points to Origin?

Sort all points by squared distance and keep the first k with time complexity O(N log N) and space complexity O(K).

What is the optimal approach and complexity for K Closest Points to Origin?

Keep the K closest points in a max-heap; pop the farthest when the heap grows past K with optimal time complexity O(N log K) and space complexity O(K).

How do you identify the pattern for K Closest Points to Origin?

Look for key signals in the prompt: "k closest to the origin" indicates We keep only K items with the smallest score, not all of them. That is Top K, so a heap of size K.; "distance from the origin" indicates The score is x² + y². Squares keep the same order, so the square root is not needed.; "in any order" indicates The answer does not need sorting, so the heap can be read out directly..

K Closest Points to Origin

Medium·LeetCode #973Basic Anchor

LeetCode

Jump:

30-Second Mental ModelHeap — Top K (Closest / distance): max-heap of size K on the squared distance

Complexity:O(N log N)→O(N log K)

Key Insight

Keep a max-heap of at most K points, keyed on x² + y². Push each point. When the heap holds K + 1 points, pop the top: the top is the farthest point, so it is the one to evict. When all points are read, the heap holds the K closest.

Core Validity Invariant

After reading any number of points, the heap holds the K closest of the points read so far. Push the new point, then pop the farthest one if there are now K + 1.

Problem

You get a list of points on a flat grid. Point i is points[i] = [xi, yi]. Its distance to the origin (0, 0) is the straight-line distance, √(xi² + yi²).

Return the k points closest to the origin. You may return them in any order. The answer is unique apart from that order.

Input

points, a list of [x, y] pairs, and an integer k.

Output

A list of k points: the ones with the smallest distance to the origin.

Example 1

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

Output: [[-2, 2]]

The distance of (1, 3) is √10 and the distance of (−2, 2) is √8. Since √8 < √10, the point (−2, 2) is closer, and we keep only one point.

Example 2

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

Output: [[3, 3], [-2, 4]] (any order)

The distances are √18, √26 and √20. The two smallest are √18 and √20, so the answer is (3, 3) and (−2, 4).

Constraints

• 1 ≤ k ≤ points.length ≤ 10^4
• −10^4 ≤ xi, yi ≤ 10^4

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
The distance has a square root in it. Do I need the square root to decide which of two points is closer?
2.
I only need k points. If a new point is closer than one I already kept, which kept point should leave?
3.
Sorting all the points works. What work is wasted when I only need the first k of the sorted list?
4.
A heap gives me one item quickly. Should it be the smallest item or the largest, if I want to throw out the farthest point?
5.
Does the answer have to come out in any particular order?

Brute force approach

Idea

Give each point its squared distance x² + y², sort all n points by it, and keep the first k. Squared distance gives the same order as the real distance, so the square root is never needed.

Thinking process

1
The answer is the k points with the smallest distance. The simplest plan is to put all points in order and read off the front.
2
Comparing squares is enough. Take (1, 3) and (−2, 2): their squares are 10 and 8. Since 8 < 10, the point (−2, 2) is closer, and √8 < √10 says the same thing.
3
After sorting by that key, the first k points are the answer.
4
Sorting puts all n points in order, but we only need the first k of them. Most of that work is wasted.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        // Sort every point by its squared distance, then keep the first k.
        // Squares are enough: if a² < b², then a is closer than b.
        sort(points.begin(), points.end(), [](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];
        });
        return vector<vector<int>>(points.begin(), points.begin() + k);
    }
};

import java.util.Arrays;

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        // Sort every point by its squared distance, then keep the first k.
        // Squares are enough: if a² < b², then a is closer than b.
        Arrays.sort(points, (a, b) -> {
            int da = a[0] * a[0] + a[1] * a[1];
            int db = b[0] * b[0] + b[1] * b[1];
            return Integer.compare(da, db);
        });
        return Arrays.copyOfRange(points, 0, k);
    }
}

from typing import List

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        # Sort every point by its squared distance, then keep the first k.
        # Squares are enough: if a² < b², then a is closer than b.
        points.sort(key=lambda p: p[0] * p[0] + p[1] * p[1])
        return points[:k]

export function kClosest(points: number[][], k: number): number[][] {
    // Sort every point by its squared distance, then keep the first k.
    // Squares are enough: if a² < b², then a is closer than b.
    points.sort((a, b) => {
        const da = a[0] * a[0] + a[1] * a[1];
        const db = b[0] * b[0] + b[1] * b[1];
        return da - db;
    });
    return points.slice(0, k);
}

Complexity

Time O(N log N)Space O(K)

Sorting n points costs O(N log N). We only keep k of them, so the heap in the next approach does the same job in O(N log K). When k is small, that is a big saving. O(K) is the output; the sort works in place.

Optimized approach

Idea

Start from brute force

Brute force sorts all n points, then throws away everything after the first k.

Find the repeated work

Sorting puts all n points in order against each other. We only need to know which k are the smallest, so most of the comparisons go to points that will be thrown away.

Define the state — what variables do I need?

heap: A max-heap of (x² + y², index). It holds at most K points. Its top is the farthest point we keep.
i: The index of the point being read now.

Define validity

After reading any number of points, the heap holds the K closest of the points read so far. Push the new point, then pop the farthest one if there are now K + 1.

Define the transitions — when does each pointer move, and why is it safe?

For each point, i = 0 … n − 1

push (x² + y², i)

A new point is a candidate for the answer until a closer point pushes it out.

The heap size is above K

pop the top

The top is the farthest of the K + 1 candidates, so it cannot be one of the K closest points read so far.

After the last point

read out the heap

It holds the K closest points. Their order does not matter, so no sort is needed.

What does the current window add to the answer?

After each point, the heap is the best K points seen so far. The last heap is the answer.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        int n = points.size();
        // Max-heap of (squared distance, index). The top is the FARTHEST point we keep,
        // so it is the one to kick out when we have too many.
        priority_queue<pair<int, int>> heap;
        for (int i = 0; i < n; i++) {
            // |x|, |y| <= 10^4, so x² + y² <= 2·10^8: an int is enough.
            int d = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            heap.push({d, i});
            if ((int)heap.size() > k) heap.pop();   // evict the farthest of the k + 1
        }
        // The heap holds exactly the k closest points, in no particular order.
        vector<vector<int>> result;
        while (!heap.empty()) {
            result.push_back(points[heap.top().second]);
            heap.pop();
        }
        return result;
    }
};

import java.util.PriorityQueue;

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int n = points.length;
        // Max-heap of (squared distance, index). The top is the FARTHEST point we keep,
        // so it is the one to kick out when we have too many.
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
        for (int i = 0; i < n; i++) {
            // |x|, |y| <= 10^4, so x² + y² <= 2·10^8: an int is enough.
            int d = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            heap.add(new int[] { d, i });
            if (heap.size() > k) {
                heap.poll(); // evict the farthest of the k + 1
            }
        }
        // The heap holds exactly the k closest points, in no particular order.
        int[][] result = new int[k][2];
        for (int i = 0; i < k; i++) {
            result[i] = points[heap.poll()[1]];
        }
        return result;
    }
}

import heapq
from typing import List

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        # Max-heap of (-squared distance, point).
        # We negate the distance because heapq is a min-heap, so the top is the farthest point.
        heap: List[tuple[int, List[int]]] = []
        for p in points:
            d = p[0] * p[0] + p[1] * p[1]
            heapq.heappush(heap, (-d, p))
            if len(heap) > k:
                heapq.heappop(heap)  # evict the farthest of the k + 1

        # The heap holds exactly the k closest points, in no particular order.
        return [p for _, p in heap]

type Item = [number, number]; // [squaredDistance, index]

class MaxHeap {
    private data: Item[] = [];

    push(val: Item): void {
        this.data.push(val);
        this.bubbleUp(this.data.length - 1);
    }

    pop(): Item | undefined {
        if (this.data.length === 0) return undefined;
        const top = this.data[0];
        const last = this.data.pop()!;
        if (this.data.length > 0) {
            this.data[0] = last;
            this.bubbleDown(0);
        }
        return top;
    }

    size(): number {
        return this.data.length;
    }

    private bubbleUp(idx: number): void {
        while (idx > 0) {
            const parent = (idx - 1) >> 1;
            if (this.data[parent][0] < this.data[idx][0]) {
                [this.data[parent], this.data[idx]] = [this.data[idx], this.data[parent]];
                idx = parent;
            } else {
                break;
            }
        }
    }

    private bubbleDown(idx: number): void {
        const len = this.data.length;
        while (true) {
            let largest = idx;
            const left = 2 * idx + 1;
            const right = 2 * idx + 2;
            if (left < len && this.data[left][0] > this.data[largest][0]) largest = left;
            if (right < len && this.data[right][0] > this.data[largest][0]) largest = right;
            if (largest !== idx) {
                [this.data[idx], this.data[largest]] = [this.data[largest], this.data[idx]];
                idx = largest;
            } else {
                break;
            }
        }
    }
}

export function kClosest(points: number[][], k: number): number[][] {
    const n = points.length;
    // Max-heap of (squared distance, index). The top is the FARTHEST point we keep,
    // so it is the one to kick out when we have too many.
    const heap = new MaxHeap();
    for (let i = 0; i < n; i++) {
        const d = points[i][0] * points[i][0] + points[i][1] * points[i][1];
        heap.push([d, i]);
        if (heap.size() > k) {
            heap.pop(); // evict the farthest of the k + 1
        }
    }

    // The heap holds exactly the k closest points, in no particular order.
    const result: number[][] = [];
    while (heap.size() > 0) {
        result.push(points[heap.pop()![1]]);
    }
    return result;
}

Complexity

Time O(N log K)Space O(K)

Each point does one push and at most one pop on a heap of size K + 1, so each costs O(log K). Quickselect (split the points around the K-th distance) takes O(N) on average, but it reorders the input and is harder to get right. Learn the heap first.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Sort all points by squared distance and keep the first k	O(N log N)	O(K)
Optimal	Keep the K closest points in a max-heap; pop the farthest when the heap grows past K	O(N log K)	O(K)

Why does this belong to this pattern?

Clues in the problem statement

“k closest to the origin”We keep only K items with the smallest score, not all of them. That is Top K, so a heap of size K.
“distance from the origin”The score is x² + y². Squares keep the same order, so the square root is not needed.
“in any order”The answer does not need sorting, so the heap can be read out directly.

Score each point: x² + y²+keep the K smallest scores+max-heap of size K→Heap — Top K (Closest / distance): max-heap of size K on the squared distance

This is the anchor of the Closest sub-pattern. We keep the K smallest scores, so the item to throw out is the largest one, and the heap must be a max-heap. Kth Largest Element is the opposite rule: keep the K largest in a min-heap, because the item to throw out is the smallest. Next in this sub-pattern is Find K Closest Elements. Its input is sorted, so the answer is a window and binary search beats the heap there.

Don't make this mistake

Min-heap of size K (pattern confusion)

✗ priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;

✓ priority_queue<pair<int, int>> heap;

A min-heap pops the SMALLEST key first, and the smallest key is the closest point, so it gets thrown out. Dry run: points = [[1, 3], [−2, 2], [5, 8], [0, 1], [−3, 4], [2, −1]] with k = 3. The min-heap throws out (0, 1), then (−2, 2), then (2, −1), which are the three closest points. It keeps (1, 3), (−3, 4) and (5, 8), which are the farthest. The max-heap keeps the right three: (−2, 2), (0, 1) and (2, −1).

Returning scores or indexes instead of points

✗ result.push_back({heap.top().first});

✓ result.push_back(points[heap.top().second]);

The answer is a list of [x, y] points. The heap holds (score, index) pairs, so read the point back from points[index]. A score such as 8 does not say which point it came from.

Pushing all n points, then popping n − K

✗ for (auto& p : points) heap.push(...); while ((int)heap.size() > k) heap.pop();

✓ for (int i = 0; i < n; i++) { heap.push(...); if ((int)heap.size() > k) heap.pop(); }

The answer is the same, but the heap now holds all n points at once. That costs O(N log N) instead of O(N log K), and O(N) memory instead of O(K). Pop as you go, so the heap never grows past K + 1.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Heap — Top K translate into production architectures and low-level memory mechanics.

LLD Real-World Story

High-Frequency Trading (HFT) Order Book

Price-time priority matching engine powered by heap buckets and tree maps.

Explore Track

C++ Internals

STL Containers & Allocator Internals

std::priority_queue container adapter and underlying heapify memory buffers.

Explore Track

Find K Closest Elements