Loading…

mediumHeapLC #973Frequently asked

K Closest Points to Origin

Q: How do you solve K Closest Points to Origin using the Max-Heap of Size K approach?

When to use it: The default answer. Lead with 'compare squared distances and keep a heap of only the k closest seen so far'. Treat it as Top-K with the key being squared distance. **Why squared distance.** Euclidean distance is `√(x²+y²)`. Since `√` is strictly increasing, comparing `x²+y²` gives the *same ordering* as comparing the true distances — but with integer arithmetic, no precision loss, and no `sqrt` calls. Always state this; it's the cheapest way to look sharp. **Why a max-heap of size k.** We want the k *smallest* distances. Counter-intuitively, keep a *max*-heap (farthest on top) capped at k. When a new point arrives and the heap is full, compare it implicitly: push it, then pop the top. The top is the farthest among the k+1 candidates, so popping it always discards the least deserving point. Whatever survives all n points is the k closest. **Why not a min-heap of everything.** Heapifying all n points into a min-heap and popping k times is `O(n + k log n)` and stores all n. The size-k max-heap caps memory at k and each operation at `log k` — better when `k ≪ n`, and it generalises to streams where n is unbounded. **Python detail.** `heapq` is a min-heap, so push `(-distance, x, y)`. The most-negative (largest true distance) sits on top and gets popped first — exactly the max-heap behaviour we want. Time complexity: O(n log k). Space complexity: O(k).

Q: How do you solve K Closest Points to Origin using the Quickselect (Optimal Average O(n)) approach?

When to use it: Offer when asked to beat O(n log k) or for the best average time. It partitions the k closest without ordering them. Quickselect finds the k smallest *without fully sorting*. **Partition like quicksort, recurse like binary search.** Pick a pivot point, then rearrange so every point with squared distance ≤ the pivot's sits left of it and every farther point sits right. The pivot is now at its final sorted index `p`. **Recurse into one side only.** If `p == k`, the first k slots hold exactly the k closest — done. If `p > k`, the answer is entirely within the left part, so recurse there. If `p < k`, the left part is fully in the answer; recurse right for the remaining `k − p`. Unlike quicksort, we discard the other half each time, which is why the expected cost collapses to linear. **Why it can beat the heap.** No `log k` factor and no auxiliary heap — it rearranges in place. The cost is a worst case of `O(n²)` on adversarial pivots, mitigated by random pivot selection. Mention this trade: heap is `O(n log k)` guaranteed, quickselect is `O(n)` average but `O(n²)` worst. **Output order is free.** Because we only need the k closest as a *set*, leaving them unsorted on the left is perfectly valid — that's what makes quickselect applicable here at all. Time complexity: O(n) average, O(n²) worst. Space complexity: O(1) extra (in place).

LCPractice

Heap & Priority Queue · 3 of 9 · 9 min

Given an array points where points[i] = [xᵢ, yᵢ] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points is the Euclidean distance: √((x₁−x₂)² + (y₁−y₂)²). You may return the answer in any order. The answer is guaranteed to be unique (except for the order).

In plain English

Select the k points nearest the origin. 'Nearest' is by Euclidean distance, but since we only compare distances, the squared distance x²+y² gives the identical ordering without any square roots. Output order doesn't matter.

Examples

Example 1

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Note: Squared distances: [1,3]→10, [-2,2]→8. 8 < 10, so [-2,2] is closer.

Example 2

Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Note: Squared distances: 18, 26, 20. The two smallest are 18 and 20 → [3,3] and [-2,4].

Example 3

Input: points = [[0,1],[1,0]], k = 2
Output: [[0,1],[1,0]]
Note: Both squared distances are 1; k equals n so both points are returned.

Constraints

1 ≤ k ≤ points.length ≤ 10⁴
-10⁴ ≤ xᵢ, yᵢ ≤ 10⁴
The answer is unique up to ordering

Clarifying questions4First question: Does the output order matter?Explore questions

Q1.Does the output order matter?
No — any order is accepted. That's why a heap (partial order) or quickselect (no order) both work; no need to sort the final k.
Q2.Can I compare squared distances instead of true distances?
Yes. Square root is monotonic, so x²+y² preserves the ordering and avoids floating-point error and cost. I'll only sqrt if actual distances are required in the output.
Q3.Could two points tie in distance at the boundary?
The problem guarantees a unique answer set, so the cutoff is well-defined. If ties were allowed I'd confirm whether any valid set of k is acceptable.
Q4.How big is k relative to n?
If k ≪ n, a size-k heap (O(n log k)) is great. If k ≈ n, just sort. Quickselect is O(n) average regardless of k.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Rank points by squared distance x²+y² (skip the square root — it's monotonic and only adds floating-point error). The interview-grade answer is a max-heap of size k: push each point, pop when size exceeds k, and the k smallest distances survive — O(n log k) time, O(k) space. For O(n)-average time, mention quickselect to partition the k closest without ordering them.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you drop the square root (monotonicity insight), and whether you select with a size-k heap instead of sorting everything — plus awareness of quickselect for O(n) average.

Where candidates slip

Computing Math.sqrt for the comparison (slower and floating-point fragile), or using a min-heap of all n points and popping k — O(n log n) and O(n) memory.

How to stand out

Say 'compare squared distances' before writing code, give the heap O(n log k) solution, then offer quickselect O(n) average and discuss its worst case and why output order is free.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Max-Heap of Size K	`O(n log k)`	`O(k)`	The default answer. Lead with 'compare squared distances and keep a heap of only the k closest seen so far'.	Read
2	Quickselect (Optimal Average O(n))Optimal	`O(n) average, O(n²) worst`	`O(1) extra (in place)`	Offer when asked to beat O(n log k) or for the best average time. It partitions the k closest without ordering them.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewk closest points to originNeed O(n) average?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Max-Heap of Size K

TimeO(n log k)SpaceO(k)

The default answer. Lead with 'compare squared distances and keep a heap of only the k closest seen so far'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You need the k smallest by a computed key. To keep 'the k best so far' while streaming, which heap orientation lets you evict the current worst?

2Hint 2Explore hint

Use a MAX-heap keyed by squared distance, capped at size k. The top is always the farthest of the k you're holding.

3Hint 3Explore hint

Push each point; if the heap exceeds k, pop the top (the farthest). After all points, the heap holds exactly the k closest.

A · Core idea

Treat it as Top-K with the key being squared distance.

Why squared distance. Euclidean distance is √(x²+y²). Since √ is strictly increasing, comparing x²+y² gives the same ordering as comparing the true distances — but with integer arithmetic, no precision loss, and no sqrt calls. Always state this; it's the cheapest way to look sharp.

Why a max-heap of size k. We want the k smallest distances. Counter-intuitively, keep a max-heap (farthest on top) capped at k. When a new point arrives and the heap is full, compare it implicitly: push it, then pop the top. The top is the farthest among the k+1 candidates, so popping it always discards the least deserving point. Whatever survives all n points is the k closest.

Why not a min-heap of everything. Heapifying all n points into a min-heap and popping k times is O(n + k log n) and stores all n. The size-k max-heap caps memory at k and each operation at log k — better when k ≪ n, and it generalises to streams where n is unbounded.

Python detail. heapq is a min-heap, so push (-distance, x, y). The most-negative (largest true distance) sits on top and gets popped first — exactly the max-heap behaviour we want.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

compute

distances 18, 26, 20

k=2 ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result[[3,3], [-2,4]]

C · Code with teaching comments

Reference implementation previewpublic int[][] kClosest(int[][] points, int k) { // Max-heap by squared distance (largest distance on top). PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> dist(b) - dist(a)); for (int[] p : points) {Explore the full code

solution.javaJava

Max-Heap of Size K — reference

3 teaching notes

1
public int[][] kClosest(int[][] points, int k) {
2
    // Max-heap by squared distance (largest distance on top).
3
    PriorityQueue<int[]> heap =
4
        // Comparator puts the LARGER squared distance on top → a max-heap, so we evict
5
        // the farthest.
6
        new PriorityQueue<>((a, b) -> dist(b) - dist(a));
7
    for (int[] p : points) {
8
        heap.offer(p);
9
        if (heap.size() > k) {
10
            heap.poll();
11
        }
12
    }
13
    int[][] res = new int[k][2];
14
    for (int i = 0; i < k; i++) {
15
        res[i] = heap.poll();
16
    }
17
    return res;
18
}
19
 
20
private int dist(int[] p) {
21
    return p[0] * p[0] + p[1] * p[1];
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n log k) timeO(k) spaceOpen the invariant and proofExplore the proof

The size-k max-heap is a bouncer keeping only the k closest in the club: the bouncer (heap top) is whoever is currently farthest, so any closer newcomer bumps them. You never compare points directly — the heap's ordering decides every eviction.

ComplexityO(n log k) time, O(k) space — Each of n points triggers a push and possibly a pop, each O(log k) because the heap never exceeds k. Total O(n log k). The heap holds at most k entries → O(k) space.

E · Edge cases and pitfalls6points = [[0,0]], k = 1 — Distance 0; single point returned. Origin itself is closest to origin.Explore edge cases

Edge cases handled

points = [[0,0]], k = 1Distance 0; single point returned. Origin itself is closest to origin.
k == points.lengthHeap never exceeds k after all pushes; every point is returned.
ties like [[1,0],[0,1]], k = 1Both distance 1; either is a valid answer — problem guarantees a unique set on real inputs.

Pitfalls

Using Math.sqrt for comparison — slower and risks floating-point ties; compare squared distances.
Building a min-heap of all n points (O(n log n), O(n) memory) instead of a size-k max-heap.
Reversing the comparator into a min-heap of size k — you'd keep the k FARTHEST points.

03.2

Approach 2 of 2 · Optimal

Quickselect (Optimal Average O(n))

TimeO(n) average, O(n²) worstSpaceO(1) extra (in place)

Offer when asked to beat O(n log k) or for the best average time. It partitions the k closest without ordering them.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You don't need the k closest sorted — you only need them grouped to the front. What algorithm partitions an array around a pivot so one side is 'smaller'?

2Hint 2Explore hint

Use quickselect (the selection cousin of quicksort): partition by squared distance so all distances ≤ pivot are on the left.

3Hint 3Explore hint

Recurse only into the side containing the boundary index k. Once the pivot lands at index k, the first k elements are the answer — in any order.

A · Core idea

Quickselect finds the k smallest without fully sorting.

Partition like quicksort, recurse like binary search. Pick a pivot point, then rearrange so every point with squared distance ≤ the pivot's sits left of it and every farther point sits right. The pivot is now at its final sorted index p.

Recurse into one side only. If p == k, the first k slots hold exactly the k closest — done. If p > k, the answer is entirely within the left part, so recurse there. If p < k, the left part is fully in the answer; recurse right for the remaining k − p. Unlike quicksort, we discard the other half each time, which is why the expected cost collapses to linear.

Why it can beat the heap. No log k factor and no auxiliary heap — it rearranges in place. The cost is a worst case of O(n²) on adversarial pivots, mitigated by random pivot selection. Mention this trade: heap is O(n log k) guaranteed, quickselect is O(n) average but O(n²) worst.

Output order is free. Because we only need the k closest as a set, leaving them unsorted on the left is perfectly valid — that's what makes quickselect applicable here at all.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

Picking the right approach

pivot = last (d=20)

Active call / nodeSupporting contextReturned stateNot active

Always compare squared distance. Then choose by k-vs-n and whether O(n) average is needed.

Final result[[3,3], [-2,4]]

C · Code with teaching comments

solution.javaJava

Quickselect (Optimal Average O(n)) — optimal

4 teaching notes

1
public int[][] kClosest(int[][] points, int k) {
2
    int lo = 0, hi = points.length - 1;
3
    while (lo < hi) {
4
        // Place the pivot at its final sorted index by squared distance; left side is
5
        // all ≤ pivot.
6
        int p = partition(points, lo, hi);
7
        // Boundary landed exactly at k — the first k points are the answer, in any
8
        // order.
9
        if (p == k) break;
10
        // Left part fully belongs to the answer; search the right for the remaining
11
        // points.
12
        else if (p < k) lo = p + 1;
13
        else hi = p - 1;
14
    }
15
    // The k closest now occupy the first k slots — copy them out.
16
    return Arrays.copyOfRange(points, 0, k);
17
}
18
 
19
private int partition(int[][] pts, int lo, int hi) {
20
    int pivot = dist(pts[hi]);
21
    int i = lo;
22
    for (int j = lo; j < hi; j++) {
23
        if (dist(pts[j]) <= pivot) {
24
            swap(pts, i++, j);
25
        }
26
    }
27
    swap(pts, i, hi);
28
    return i;
29
}
30
 
31
private int dist(int[] p) { return p[0]*p[0] + p[1]*p[1]; }
32
 
33
private void swap(int[][] pts, int a, int b) {
34
    int[] t = pts[a]; pts[a] = pts[b]; pts[b] = t;
35
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.35 lines

D · Why it works and complexityO(n) average, O(n²) worst timeO(1) extra (in place) spaceOpen the invariant and proofExplore the proof

Sorting answers 'what is the full order?' but the question only asks 'which k are smallest?'. Quickselect exploits that weaker requirement: it stops the instant the boundary is placed, never paying for order it doesn't need — the canonical 'selection, not sorting' optimization.

ComplexityO(n) average, O(n²) worst time, O(1) extra (in place) space — Each partition is O(n) and quickselect recurses into only one side, so expected work is n + n/2 + n/4 + … = O(n). A pathological pivot sequence degrades to O(n²); randomising the pivot makes that astronomically unlikely.

E · Edge cases and pitfalls6k == 1 — Quickselect drives the single minimum to index 0; return that one point.Explore edge cases

Edge cases handled

k == 1Quickselect drives the single minimum to index 0; return that one point.
all equal distancesEvery comparison is ≤ pivot; partition still terminates and any k are valid.
k == nLoop exits immediately (boundary trivially satisfied); return all points.

Pitfalls

Recursing into BOTH sides — that's quicksort (O(n log n)), defeating the point of quickselect.
Off-by-one on the boundary (using p vs p+1) — return the wrong count of points.
Not randomising the pivot — sorted/adversarial input degrades to O(n²).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int[][] kClosest(int[][] points, int k) { int lo = 0, hi = points.length - 1; while (lo < hi) { int p = partition(points, lo, hi); if (p == k) break;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Taking the square root unnecessarily

sqrt is monotonic, so it never changes the ordering — it only adds cost and floating-point error that can mis-order near-ties.

Explore the code comparison

Don't write this

import math
d = math.sqrt(x * x + y * y)  # float, slower, can mis-tie
heapq.heappush(heap, (-d, x, y))

Write this instead

d = x * x + y * y  # integer squared distance, exact ordering
heapq.heappush(heap, (-d, x, y))

Min-heap of all points instead of size-k max-heap

Heapifying all n and popping k is O(n + k log n) and holds every point. A size-k max-heap is O(n log k) and O(k) memory — strictly better when k ≪ n.

Explore the code comparison

Don't write this

PriorityQueue<int[]> heap =
    new PriorityQueue<>((a, b) -> dist(a) - dist(b)); // min-heap of all n
for (int[] p : points) heap.offer(p);
int[][] res = new int[k][2];
for (int i = 0; i < k; i++) res[i] = heap.poll();

Write this instead

PriorityQueue<int[]> heap =
    new PriorityQueue<>((a, b) -> dist(b) - dist(a)); // max-heap, size k
for (int[] p : points) {
    heap.offer(p);
    if (heap.size() > k) heap.poll();
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Size-k max-heap on squared distance (or quickselect)

Code pattern to memorize

heap = []                       # max-heap of (-dist, point)
for (x, y) in points:
    d = x*x + y*y
    heappush(heap, (-d, x, y))
    if len(heap) > k: heappop(heap)
return [[x, y] for d, x, y in heap]

Rules to remember

1Compare squared distance x²+y², never sqrt — sqrt is monotonic so ordering is identical, and it avoids float error and cost.
2Use a max-heap of size k (largest distance on top) so the farthest of the current k is evicted when a closer point arrives.
3Python's min-heap → negate the distance to get a max-heap.
4The output order is unspecified — don't waste time sorting the final k unless asked.
5If the interviewer wants O(n) average, switch to quickselect (partition around the k-th distance).

Use this pattern when

'K closest / nearest / smallest by a computed key' problems
You need the k best by a metric without a full sort
Streaming points where k stays small relative to n
Any nearest-neighbour-style selection with a cheap distance proxy

Choose another pattern when

k ≈ n → just sort all points by distance
You need them sorted by distance → sort directly, O(n log n)
k = 1 → linear scan for the single minimum
Need exact Euclidean distances for output → only then take sqrt at the end

Interview takeaway

K Closest is Top-K wearing a geometry costume: the only twist is the key (squared distance). A size-k max-heap gives O(n log k); quickselect gives O(n) average. Recognise it as the same bounded-heap pattern as Top K Frequent and Kth Largest.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternTop-K selection by a computed key (squared distance). Size-k max-heap is O(n log k); quickselect is O(n) average. Same family as Kth Largest Element and Top K Frequent Elements — recognise the 'k best by a key' shape.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Kth Largest Element in an Array
Coming soon
Same size-k heap or quickselect, keyed by value rather than distance.
Top K Frequent Elements
Identical bounded-heap pattern; the key is frequency instead of distance.
Find K Closest Elements
Coming soon
On a sorted array — binary search the window start, then take k contiguous elements.
Last Stone Weight
Coming soon
A pure max-heap warm-up: repeatedly smash the two heaviest stones.

Same pattern

←

Find Median from Data Stream

Continue · Next problem

Task Scheduler

mediumHeapLC #973Frequently asked

K Closest Points to Origin

LCPractice

Heap & Priority Queue · 3 of 9 · 9 min

Given an array points where points[i] = [xᵢ, yᵢ] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

In plain English

Examples

Example 1

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Note: Squared distances: [1,3]→10, [-2,2]→8. 8 < 10, so [-2,2] is closer.

Example 2

Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Note: Squared distances: 18, 26, 20. The two smallest are 18 and 20 → [3,3] and [-2,4].

Example 3

Input: points = [[0,1],[1,0]], k = 2
Output: [[0,1],[1,0]]
Note: Both squared distances are 1; k equals n so both points are returned.

Constraints

1 ≤ k ≤ points.length ≤ 10⁴
-10⁴ ≤ xᵢ, yᵢ ≤ 10⁴
The answer is unique up to ordering

Clarifying questions4First question: Does the output order matter?Explore questions

Q1.Does the output order matter?
No — any order is accepted. That's why a heap (partial order) or quickselect (no order) both work; no need to sort the final k.
Q2.Can I compare squared distances instead of true distances?
Yes. Square root is monotonic, so x²+y² preserves the ordering and avoids floating-point error and cost. I'll only sqrt if actual distances are required in the output.
Q3.Could two points tie in distance at the boundary?
The problem guarantees a unique answer set, so the cutoff is well-defined. If ties were allowed I'd confirm whether any valid set of k is acceptable.
Q4.How big is k relative to n?
If k ≪ n, a size-k heap (O(n log k)) is great. If k ≈ n, just sort. Quickselect is O(n) average regardless of k.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you drop the square root (monotonicity insight), and whether you select with a size-k heap instead of sorting everything — plus awareness of quickselect for O(n) average.

Where candidates slip

Computing Math.sqrt for the comparison (slower and floating-point fragile), or using a min-heap of all n points and popping k — O(n log n) and O(n) memory.

How to stand out

Say 'compare squared distances' before writing code, give the heap O(n log k) solution, then offer quickselect O(n) average and discuss its worst case and why output order is free.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Max-Heap of Size K	`O(n log k)`	`O(k)`	The default answer. Lead with 'compare squared distances and keep a heap of only the k closest seen so far'.	Read
2	Quickselect (Optimal Average O(n))Optimal	`O(n) average, O(n²) worst`	`O(1) extra (in place)`	Offer when asked to beat O(n log k) or for the best average time. It partitions the k closest without ordering them.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Max-Heap of Size K

TimeO(n log k)SpaceO(k)

The default answer. Lead with 'compare squared distances and keep a heap of only the k closest seen so far'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You need the k smallest by a computed key. To keep 'the k best so far' while streaming, which heap orientation lets you evict the current worst?

2Hint 2Explore hint

Use a MAX-heap keyed by squared distance, capped at size k. The top is always the farthest of the k you're holding.

3Hint 3Explore hint

Push each point; if the heap exceeds k, pop the top (the farthest). After all points, the heap holds exactly the k closest.

A · Core idea

Treat it as Top-K with the key being squared distance.

Python detail. heapq is a min-heap, so push (-distance, x, y). The most-negative (largest true distance) sits on top and gets popped first — exactly the max-heap behaviour we want.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

compute

distances 18, 26, 20

k=2 ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result[[3,3], [-2,4]]

C · Code with teaching comments

solution.javaJava

Max-Heap of Size K — reference

3 teaching notes

1
public int[][] kClosest(int[][] points, int k) {
2
    // Max-heap by squared distance (largest distance on top).
3
    PriorityQueue<int[]> heap =
4
        // Comparator puts the LARGER squared distance on top → a max-heap, so we evict
5
        // the farthest.
6
        new PriorityQueue<>((a, b) -> dist(b) - dist(a));
7
    for (int[] p : points) {
8
        heap.offer(p);
9
        if (heap.size() > k) {
10
            heap.poll();
11
        }
12
    }
13
    int[][] res = new int[k][2];
14
    for (int i = 0; i < k; i++) {
15
        res[i] = heap.poll();
16
    }
17
    return res;
18
}
19
 
20
private int dist(int[] p) {
21
    return p[0] * p[0] + p[1] * p[1];
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n log k) timeO(k) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6points = [[0,0]], k = 1 — Distance 0; single point returned. Origin itself is closest to origin.Explore edge cases

Edge cases handled

points = [[0,0]], k = 1Distance 0; single point returned. Origin itself is closest to origin.
k == points.lengthHeap never exceeds k after all pushes; every point is returned.
ties like [[1,0],[0,1]], k = 1Both distance 1; either is a valid answer — problem guarantees a unique set on real inputs.

Pitfalls

Using Math.sqrt for comparison — slower and risks floating-point ties; compare squared distances.
Building a min-heap of all n points (O(n log n), O(n) memory) instead of a size-k max-heap.
Reversing the comparator into a min-heap of size k — you'd keep the k FARTHEST points.

03.2

Approach 2 of 2 · Optimal

Quickselect (Optimal Average O(n))

TimeO(n) average, O(n²) worstSpaceO(1) extra (in place)

Offer when asked to beat O(n log k) or for the best average time. It partitions the k closest without ordering them.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You don't need the k closest sorted — you only need them grouped to the front. What algorithm partitions an array around a pivot so one side is 'smaller'?

2Hint 2Explore hint

Use quickselect (the selection cousin of quicksort): partition by squared distance so all distances ≤ pivot are on the left.

3Hint 3Explore hint

Recurse only into the side containing the boundary index k. Once the pivot lands at index k, the first k elements are the answer — in any order.

A · Core idea

Quickselect finds the k smallest without fully sorting.

Output order is free. Because we only need the k closest as a set, leaving them unsorted on the left is perfectly valid — that's what makes quickselect applicable here at all.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

Picking the right approach

pivot = last (d=20)

Active call / nodeSupporting contextReturned stateNot active

Always compare squared distance. Then choose by k-vs-n and whether O(n) average is needed.

Final result[[3,3], [-2,4]]

C · Code with teaching comments

solution.javaJava

Quickselect (Optimal Average O(n)) — optimal

4 teaching notes

1
public int[][] kClosest(int[][] points, int k) {
2
    int lo = 0, hi = points.length - 1;
3
    while (lo < hi) {
4
        // Place the pivot at its final sorted index by squared distance; left side is
5
        // all ≤ pivot.
6
        int p = partition(points, lo, hi);
7
        // Boundary landed exactly at k — the first k points are the answer, in any
8
        // order.
9
        if (p == k) break;
10
        // Left part fully belongs to the answer; search the right for the remaining
11
        // points.
12
        else if (p < k) lo = p + 1;
13
        else hi = p - 1;
14
    }
15
    // The k closest now occupy the first k slots — copy them out.
16
    return Arrays.copyOfRange(points, 0, k);
17
}
18
 
19
private int partition(int[][] pts, int lo, int hi) {
20
    int pivot = dist(pts[hi]);
21
    int i = lo;
22
    for (int j = lo; j < hi; j++) {
23
        if (dist(pts[j]) <= pivot) {
24
            swap(pts, i++, j);
25
        }
26
    }
27
    swap(pts, i, hi);
28
    return i;
29
}
30
 
31
private int dist(int[] p) { return p[0]*p[0] + p[1]*p[1]; }
32
 
33
private void swap(int[][] pts, int a, int b) {
34
    int[] t = pts[a]; pts[a] = pts[b]; pts[b] = t;
35
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.35 lines

D · Why it works and complexityO(n) average, O(n²) worst timeO(1) extra (in place) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6k == 1 — Quickselect drives the single minimum to index 0; return that one point.Explore edge cases

Edge cases handled

k == 1Quickselect drives the single minimum to index 0; return that one point.
all equal distancesEvery comparison is ≤ pivot; partition still terminates and any k are valid.
k == nLoop exits immediately (boundary trivially satisfied); return all points.

Pitfalls

Recursing into BOTH sides — that's quicksort (O(n log n)), defeating the point of quickselect.
Off-by-one on the boundary (using p vs p+1) — return the wrong count of points.
Not randomising the pivot — sorted/adversarial input degrades to O(n²).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int[][] kClosest(int[][] points, int k) { int lo = 0, hi = points.length - 1; while (lo < hi) { int p = partition(points, lo, hi); if (p == k) break;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Taking the square root unnecessarily

sqrt is monotonic, so it never changes the ordering — it only adds cost and floating-point error that can mis-order near-ties.

Explore the code comparison

Don't write this

import math
d = math.sqrt(x * x + y * y)  # float, slower, can mis-tie
heapq.heappush(heap, (-d, x, y))

Write this instead

d = x * x + y * y  # integer squared distance, exact ordering
heapq.heappush(heap, (-d, x, y))

Min-heap of all points instead of size-k max-heap

Heapifying all n and popping k is O(n + k log n) and holds every point. A size-k max-heap is O(n log k) and O(k) memory — strictly better when k ≪ n.

Explore the code comparison

Don't write this

PriorityQueue<int[]> heap =
    new PriorityQueue<>((a, b) -> dist(a) - dist(b)); // min-heap of all n
for (int[] p : points) heap.offer(p);
int[][] res = new int[k][2];
for (int i = 0; i < k; i++) res[i] = heap.poll();

Write this instead

PriorityQueue<int[]> heap =
    new PriorityQueue<>((a, b) -> dist(b) - dist(a)); // max-heap, size k
for (int[] p : points) {
    heap.offer(p);
    if (heap.size() > k) heap.poll();
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Size-k max-heap on squared distance (or quickselect)

Code pattern to memorize

heap = []                       # max-heap of (-dist, point)
for (x, y) in points:
    d = x*x + y*y
    heappush(heap, (-d, x, y))
    if len(heap) > k: heappop(heap)
return [[x, y] for d, x, y in heap]

Rules to remember

1Compare squared distance x²+y², never sqrt — sqrt is monotonic so ordering is identical, and it avoids float error and cost.
2Use a max-heap of size k (largest distance on top) so the farthest of the current k is evicted when a closer point arrives.
3Python's min-heap → negate the distance to get a max-heap.
4The output order is unspecified — don't waste time sorting the final k unless asked.
5If the interviewer wants O(n) average, switch to quickselect (partition around the k-th distance).

Use this pattern when

'K closest / nearest / smallest by a computed key' problems
You need the k best by a metric without a full sort
Streaming points where k stays small relative to n
Any nearest-neighbour-style selection with a cheap distance proxy

Choose another pattern when

k ≈ n → just sort all points by distance
You need them sorted by distance → sort directly, O(n log n)
k = 1 → linear scan for the single minimum
Need exact Euclidean distances for output → only then take sqrt at the end

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Kth Largest Element in an Array
Coming soon
Same size-k heap or quickselect, keyed by value rather than distance.
Top K Frequent Elements
Identical bounded-heap pattern; the key is frequency instead of distance.
Find K Closest Elements
Coming soon
On a sorted array — binary search the window start, then take k contiguous elements.
Last Stone Weight
Coming soon
A pure max-heap warm-up: repeatedly smash the two heaviest stones.

Same pattern

←

Find Median from Data Stream

Continue · Next problem

Task Scheduler