Log inSign up
mediumLeetCodeNot Started

K Closest Points to Origin

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on LeetCode
Lesson

Problem Statement

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

Distance is calculated using Euclidean distance: sqrt(x^2 + y^2). Since we only care about relative order, comparing x^2 + y^2 directly avoids floating point square roots.

Example 1 · Example 1: Standard Points:

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation: Distance of [1, 3] to origin is sqrt(12 + 32) = sqrt(10). Distance of [-2, 2] to origin is sqrt((-2)^2 + 22) = sqrt(8). Since sqrt(8) < sqrt(10), [-2, 2] is closer. Max-Heap (Size 1): ([-2, 2]: dist 8)

Example 2 · Example 2: Multiple Points:

Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: Distances squared: [3, 3] -> 18, [5, -1] -> 26, [-2, 4] -> 20. The 2 closest are [3, 3] and [-2, 4].

Constraints:

  • 1 <= k <= points.length <= 104
  • -104 <= xi, yi <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Avoid floating-point calculations by comparing squared distances.
  • Implement the size-K Max-Heap pattern for 'K smallest/closest' queries.
  • Understand Quickselect partitioning for expected linear selection.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find Top K / K closest items from an unsorted collection.
  • Distance metric is monotonic.
  • Answer can be returned in any order.

Algorithmic Decision Tree:

  • Use Max-Heap of size K when streaming data or K << N.
  • Use Quickselect when array is already in memory and expected linear time is required.

Connected Patterns:

Find K Closest ElementsKth Largest Element in an ArrayTop K Frequent Elements

1. Brute Force — Full Sort by Distance

Intuition

Sort the points array using a lambda comparing x12 + y12 with x22 + y22. Slice the first k elements.

When to apply: When simplicity is desired and N is small.

Algorithm

  1. Step 1: Sort points using comparator: (x1*x1 + y1*y1) - (x2*x2 + y2*y2).
  2. Step 2: Return first k elements.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
9 sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
10 return (a[0]*a[0] + a[1]*a[1]) < (b[0]*b[0] + b[1]*b[1]);
11 });
12 return vector<vector<int>>(points.begin(), points.begin() + k);
13 }
14};
15
16int main() {
17 Solution sol;
18 vector<vector<int>> points = {{3, 3}, {5, -1}, {-2, 4}};
19 auto res = sol.kClosest(points, 2);
20 cout << "K Closest (Brute Force): ";
21 for (auto& p : res) cout << "[" << p[0] << "," << p[1] << "] ";
22 cout << endl;
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(N log N) — O(N log N) from comparison sorting.
  • Space complexity: O(1) auxiliary — O(1) extra memory beyond sorting.

Why Brute Force Doesn't Scale:

For N = 105, full sorting takes ~1.7 * 106 operations, while Quickselect runs in ~105 operations.

Quickselect executes in ~5ms vs ~45ms for full sorting.

2. Better — Max-Heap of Size K

Intuition

Keep the K closest points seen so far in a Max-Heap. The root contains the largest distance among the K closest. For each point, if heap size < K, push. Else if point distance < root, pop root and push point.

When to apply: When memory is bounded or points arrive via a stream.

Algorithm

  1. Step 1: Initialize Max-Heap with comparator comparing squared distances.
  2. Step 2: For each point [x, y]: calculate dist = x*x + y*y.
  3. Step 3: If heap size < k: push point.
  4. Step 4: Else if dist < heap.top distance: pop root, push point.
  5. Step 5: Collect all points from heap and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4using namespace std;
5
6class Solution {
7public:
8 vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
9 auto comp = [](const vector<int>& a, const vector<int>& b) {
10 return (a[0]*a[0] + a[1]*a[1]) < (b[0]*b[0] + b[1]*b[1]);
11 };
12 priority_queue<vector<int>, vector<vector<int>>, decltype(comp)> maxHeap(comp);
13
14 for (auto& p : points) {
15 maxHeap.push(p);
16 if ((int)maxHeap.size() > k) {
17 maxHeap.pop();
18 }
19 }
20
21 vector<vector<int>> result;
22 while (!maxHeap.empty()) {
23 result.push_back(maxHeap.top());
24 maxHeap.pop();
25 }
26 return result;
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<vector<int>> points = {{3, 3}, {5, -1}, {-2, 4}};
33 auto res = sol.kClosest(points, 2);
34 cout << "K Closest (Max-Heap): ";
35 for (auto& p : res) cout << "[" << p[0] << "," << p[1] << "] ";
36 cout << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N log K) — O(N log K) bounded by heap size K.
  • Space complexity: O(K) — O(K) auxiliary memory.

3. Optimal — Quickselect (Hoare's Selection)

Intuition

Quickselect repeatedly partitions the array around a pivot element. If pivot index equals k, all elements to the left are the k closest points. If pivot index < k, recurse on right partition; otherwise on left partition.

When to apply: When linear time in-place selection is optimal and input array modification is permitted.

Algorithm

  1. Step 1: Set left = 0, right = points.length - 1.
  2. Step 2: Choose pivot index, partition elements smaller than pivot to left.
  3. Step 3: If pivot index == k, return points[0 ... k - 1].
  4. Step 4: If pivot index < k, search in right partition [pivot + 1, right].
  5. Step 5: Else search in left partition [left, pivot - 1].

Interactive Trace for K Closest Points to Origin

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Process [3,3] (dist 18) and [5,-1] (dist 26)
Visual state
Values and pointers at this exact step
tree
Root: [5,-1] (d: 26)
26
Child: [3,3] (d: 18)
18

Node order shown; add connections to display explicit tree edges.

top: p1
Check / comparison
Root is [5,-1] with max distance 26.
Decision / next transition
Next element will be compared against 26.
Why this step matters

Step 1: Process [3,3] (dist 18) and [5,-1] (dist 26). Heap reaches capacity k=2.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5class Solution {
6 int dist(const vector<int>& p) {
7 return p[0] * p[0] + p[1] * p[1];
8 }
9
10 int partition(vector<vector<int>>& points, int left, int right) {
11 int pivotDist = dist(points[right]);
12 int pIndex = left;
13 for (int i = left; i < right; i++) {
14 if (dist(points[i]) <= pivotDist) {
15 swap(points[i], points[pIndex]);
16 pIndex++;
17 }
18 }
19 swap(points[pIndex], points[right]);
20 return pIndex;
21 }
22
23public:
24 vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
25 int left = 0, right = points.size() - 1;
26 while (left <= right) {
27 int pIndex = partition(points, left, right);
28 if (pIndex == k) break;
29 else if (pIndex < k) left = pIndex + 1;
30 else right = pIndex - 1;
31 }
32 return vector<vector<int>>(points.begin(), points.begin() + k);
33 }
34};
35
36int main() {
37 Solution sol;
38 vector<vector<int>> points = {{3, 3}, {5, -1}, {-2, 4}};
39 auto res = sol.kClosest(points, 2);
40 cout << "K Closest (Quickselect): ";
41 for (auto& p : res) cout << "[" << p[0] << "," << p[1] << "] ";
42 cout << endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N) average, O(N^2) worst case — O(N) expected linear time.
  • Space complexity: O(1) auxiliary — O(1) auxiliary memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Full Sort by DistanceO(N log N)O(1) auxiliarySort entire array of points by x2 + y2 ascending and take first k points.Full sorting.
2.Better — Max-Heap of Size KO(N log K)O(K)Maintain Max-Heap of size K. When full and new point is closer, pop and insert.Log K per heap update.
3.Optimal — Quickselect (Hoare's Partition)OptimalO(N) average, O(N^2) worst caseO(1) auxiliaryPartition points around a pivot until the pivot index equals k.Pivot selection.

Common Pitfalls & Crucial Edge Cases

Computing square roots

sqrt introduces precision loss and slow floating-point ops; keep values squared.

Using Min-Heap of size N instead of Max-Heap of size K

Size N heap consumes O(N) memory and takes O(N log N) time.

Returning elements in specific order

The question allows any order; sorting the output is unnecessary.

Crucial Edge Cases to Validate:

  • k == points.length — Entire array is returned.
  • k == 1 — Equivalent to finding single minimum distance point in O(N).
  • Points with identical distances — Quickselect and Heap handle duplicate distances consistently.
  • Negative coordinates — Squared distances are strictly positive.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention that sqrt can be omitted immediately.
  2. Present Max-Heap of size K as the optimal streaming approach and Quickselect as the optimal in-memory algorithm.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why should we avoid computing sqrt(x2 + y2) when comparing distances to the origin?

Back to DSA Sheet