Closest Points to Origin

84.8k
0

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

Closeness follows Euclidean distance. The returned points may appear in any order, and the valid set of closest points is guaranteed to be unique apart from ordering.

Example 1

Input: points = [[1, 3], [-2, 2], [5, 8], [0, 1]], k = 2
Output: [[-2, 2], [0, 1]]
Explanation: Squared distances are 10, 8, 89, and 1. Points [0, 1] and [-2, 2] have the two smallest values. Output order may differ.

Example 2

Input: points = [[2, 4], [-1, -1], [0, 0]], k = 1
Output: [[0, 0]]
Explanation: Point [0, 0] has squared distance 0, the smallest possible distance from the origin.

Brute Force Approach

The distance of each point from the origin can be compared using x² + y². Taking the square root is unnecessary because a smaller squared distance always means a smaller actual distance.

By sorting all points using this squared distance, the closest points move to the beginning of the array. The first k points are then the required answer. This approach is simple, but it sorts every point even though only k points are needed.

Algorithm

  • Calculate squared distance as x × x + y × y so comparisons can be made without using square roots.

  • Sort all points in increasing order of squared distance, because points closer to the origin should appear first.

  • Use a sufficiently wide integer type for distance calculations, because squaring large coordinates may exceed normal integer limits.

  • Keep any order among points having the same distance because the problem allows the result in any order.

  • Take the first k points from the sorted array because they have the smallest distances.

  • Return these k points as the result.

Dry Run

closest-points-to-origin-brute-force-logo-removed-final.png

closest-points-to-origin-brute-force-logo-removed-final.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Calculates squared distance from the origin.
long long squaredDistance(vector<int>& point) {
long long x = point[0];
long long y = point[1];
// Squared values preserve distance ordering.
return x * x + y * y;
}
public:
// Returns the k closest points after sorting.
vector<vector<int>> kClosest(
vector<vector<int>>& points, int k
) {
// Sorts nearer points before farther points.
sort(
points.begin(),
points.end(),
[&](vector<int> first, vector<int> second) {
return squaredDistance(first) <
squaredDistance(second);
}
);
// Copies exactly the nearest k sorted points.
vector<vector<int>> answer(
points.begin(), points.begin() + k
);
// The sorted prefix forms the required result.
return answer;
}
};
// Driver code
int main() {
vector<vector<int>> points = {
{1, 3}, {-2, 2}, {5, 8}, {0, 1}
};
int k = 2;
Solution obj;
vector<vector<int>> answer = obj.kClosest(points, k);
cout << "[";
for (int index = 0; index < answer.size(); index++) {
cout << "[" << answer[index][0] << ", "
<< answer[index][1] << "]";
cout << (index + 1 < answer.size() ? ", " : "");
}
cout << "]" << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), where N is the number of points, because sorting all N points by squared distance dominates the work.

Space Complexity: O(N), because sorting-library storage and the returned points may require up to linear space across the implementations.

Better Approach

Sorting all points is unnecessary because only the closest k points matter. A max-heap of size k keeps only these useful candidates, with the farthest among them always available at the top.

Whenever the heap grows beyond k, remove the farthest point because it cannot remain among the current k closest points. After all points are processed, the heap contains exactly the required k nearest points.

Algorithm

  • Create an empty max-heap so the farthest retained point always stays at the top.

  • For each point, calculate its squared distance as x × x + y × y, because square roots are not needed for comparison.

  • Insert the squared distance along with the point into the heap.

  • If the heap size becomes greater than k, remove the top point because it is the farthest among the current candidates.

  • Continue processing all points so every point gets a chance to enter the closest k.

  • After traversal, extract all remaining points from the heap because they are the globally closest k points.

  • Return these points in any order because the result does not require a specific ordering.

Dry Run

Closest Points to Origin better

Closest Points to Origin better

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Calculates squared distance from the origin.
long long squaredDistance(vector<int>& point) {
long long x = point[0];
long long y = point[1];
// Squared values preserve distance ordering.
return x * x + y * y;
}
public:
// Returns the k closest points with a max heap.
vector<vector<int>> kClosest(
vector<vector<int>>& points, int k
) {
// Keeps the farthest candidate at the top.
priority_queue<
pair<long long, vector<int>>
> maxHeap;
// Tests every point against the saved candidates.
for (vector<int> point : points) {
// Stores distance beside matching coordinates.
long long distance = squaredDistance(point);
maxHeap.push({distance, point});
// Excess size exposes one removable candidate.
if (maxHeap.size() > k) {
maxHeap.pop();
}
}
vector<vector<int>> answer;
// Extracts all surviving nearest candidates.
while (!maxHeap.empty()) {
answer.push_back(maxHeap.top().second);
maxHeap.pop();
}
// Heap order is valid for arbitrary output order.
return answer;
}
};
// Driver code
int main() {
vector<vector<int>> points = {
{1, 3}, {-2, 2}, {5, 8}, {0, 1}
};
int k = 2;
Solution obj;
vector<vector<int>> answer = obj.kClosest(points, k);
cout << "[";
for (int index = 0; index < answer.size(); index++) {
cout << "[" << answer[index][0] << ", "
<< answer[index][1] << "]";
cout << (index + 1 < answer.size() ? ", " : "");
}
cout << "]" << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log k), where N is the number of points, because each point performs heap operations on a heap containing at most k + 1 entries.

Space Complexity: O(k), because the bounded max-heap and returned result store at most k points.

Optimal Approach

Quickselect avoids sorting all points by using Quicksort-style partitioning based on squared Euclidean distance, x² + y². A pivot divides the active range so that points with distance no greater than the pivot are placed on one side and points with larger distance on the other. These partitions are not sorted internally; they only satisfy the partition condition around the pivot.

After each partition, only the side containing index k - 1 needs further processing. If the pivot reaches index k - 1, the partition invariant guarantees that the first k positions contain points whose distances are no greater than the points after them, so those first k points form a valid answer. On average, the active range keeps shrinking, giving linear expected time, although consistently poor pivots can lead to quadratic time.

Algorithm

  • Set left = 0, right = n - 1, and target index k - 1.

  • Compare points using their squared Euclidean distance x² + y², because taking the square root is unnecessary for distance comparison.

  • Choose the middle point of the active range as the pivot.

  • Move the pivot to the right boundary so the active range can be partitioned with one scan.

  • Place every point whose squared distance is no greater than the pivot's distance into the left portion.

    • The points on either side are not sorted; they only satisfy the partition condition.

  • Place the pivot in its final partition position.

  • Compare the pivot index with k - 1.

    • If they are equal, stop because the partition invariant guarantees that the first k positions contain a valid set of the k closest points.

    • If the pivot index is smaller, continue in the right portion.

    • If the pivot index is larger, continue in the left portion.

  • Return the first k points after Quickselect finishes.

Dry Run

closest-points-to-origin-optimal

closest-points-to-origin-optimal

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Calculates squared distance from the origin.
long long squaredDistance(vector<int>& point) {
long long x = point[0];
long long y = point[1];
// Squared values preserve distance ordering.
return x * x + y * y;
}
// Exchanges two points inside the array.
void swapPoints(
vector<vector<int>>& points,
int first,
int second
) {
vector<int> saved = points[first];
points[first] = points[second];
points[second] = saved;
}
// Places one pivot at a valid distance rank.
int partition(
vector<vector<int>>& points,
int left,
int right
) {
int pivotIndex = left + (right - left) / 2;
long long pivotDistance =
squaredDistance(points[pivotIndex]);
// Right boundary keeps the pivot outside the scan.
swapPoints(points, pivotIndex, right);
int storeIndex = left;
// Collects no-farther points before the pivot.
for (int index = left; index < right; index++) {
long long distance = squaredDistance(points[index]);
// Eligible distance belongs in the left group.
if (distance <= pivotDistance) {
swapPoints(points, storeIndex, index);
storeIndex++;
}
}
// Pivot closes the left partition at a valid rank.
swapPoints(points, storeIndex, right);
return storeIndex;
}
public:
// Returns the k closest points with Quickselect.
vector<vector<int>> kClosest(
vector<vector<int>>& points, int k
) {
int left = 0;
int right = points.size() - 1;
int target = k - 1;
// Narrows selection toward the kth boundary.
while (left <= right) {
int pivotIndex = partition(points, left, right);
// Matching rank confirms the nearest prefix.
if (pivotIndex == target) {
break;
}
// Smaller pivot rank keeps the right segment.
if (pivotIndex < target) {
left = pivotIndex + 1;
} else {
right = pivotIndex - 1;
}
}
// Copies exactly the selected nearest prefix.
vector<vector<int>> answer(
points.begin(), points.begin() + k
);
// Partitioned prefix forms the required result.
return answer;
}
};
// Driver code
int main() {
vector<vector<int>> points = {
{1, 3}, {-2, 2}, {5, 8}, {0, 1}
};
int k = 2;
Solution obj;
vector<vector<int>> answer = obj.kClosest(points, k);
cout << "[";
for (int index = 0; index < answer.size(); index++) {
cout << "[" << answer[index][0] << ", "
<< answer[index][1] << "]";
cout << (index + 1 < answer.size() ? ", " : "");
}
cout << "]" << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N) on average, where N is the number of points, because Quickselect repeatedly partitions only the side containing the required k closest points. In the worst case, repeatedly unbalanced pivots lead to O(N2) time.

Space Complexity: O(k), because iterative in-place partitioning uses O(1) auxiliary space, while the returned result stores k points.

Interview follow-up Questions

No. Squared distance x * x + y * y preserves Euclidean-distance ordering and avoids unnecessary floating-point work.

Heap

Read Similar Blogs

Heap

Find K Pairs with Smallest Sums

Given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k , form every index-pair [firstIndex, secondIndex] . The sum of an index-pair is nums1[firstInd...

61.1k
Heap

Introduction to Heap

Imagine an emergency room with several waiting patients. The patient needing the most urgent care is treated first, even if another patient arrived earlier. The next choice depends on priority, not...

72.8k
Heap

Meeting Rooms II

Given an array intervals , where every entry [start, end] represents one meeting, find the minimum number of conference rooms needed to hold every meeting without a scheduling conflict. An end time...

57.7k
Comments0