Given an array points
representing n
points in a 2D plane, where points[i] = [x_i, y_i]
, and an integer k
, find the k
closest points to the origin (0, 0).
The distance between two points on the plane is the Euclidean distance (i.e., sqrt(x^2 + y^2)
).
Return the k
closest points in any order. It is guaranteed that the answer exists.
Table of Contents
Example:
Input:
points = [[1, 3], [-2, 2]]
k = 1
Output:
[[-2, 2]]
Explanation: In the input, the Euclidean distance from [1, 3]
to the origin is sqrt(1^2 + 3^2) = sqrt(10)
, and the distance from [-2, 2]
to the origin is sqrt((-2)^2 + 2^2) = sqrt(8)
. Since k=1
, the closest point to the origin is [-2, 2]
.
Solution in C++:
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
// Function to find k closest points to the origin
std::vector<std::vector<int>> kClosest(std::vector<std::vector<int>>& points, int k) {
// Create a max heap priority queue to store points based on their distance to the origin
std::priority_queue<std::pair<int, std::vector<int>>> maxHeap;
// Calculate the squared distances of each point from the origin and add them to the max heap
for (const auto& point : points) {
int x = point[0];
int y = point[1];
int distance = x * x + y * y;
maxHeap.push(std::make_pair(distance, point));
// Keep the size of the max heap at most k
if (maxHeap.size() > k) {
maxHeap.pop();
}
}
// Extract the k closest points from the max heap and store them in the result vector
std::vector<std::vector<int>> result;
while (!maxHeap.empty()) {
result.push_back(maxHeap.top().second);
maxHeap.pop();
}
return result;
}
int main() {
std::vector<std::vector<int>> points = {{1, 3}, {-2, 2}, {5, 4}};
int k = 2;
std::vector<std::vector<int>> result = kClosest(points, k);
std::cout << "The " << k << " closest points to the origin are:\n";
for (const auto& point : result) {
std::cout << "[" << point[0] << ", " << point[1] << "] ";
}
std::cout << std::endl;
return 0;
}
Explanation:
- The
kClosest
function takes a reference to a vector of vectorspoints
and an integerk
. - We create a max heap priority queue
maxHeap
to store pairs of squared distances and the corresponding point in the form[distance, point]
. By using a max heap, we ensure that the points with the largest squared distances (i.e., farthest from the origin) are at the top of the heap, and we can easily pop them when the heap size exceedsk
. - We iterate through each point in the
points
vector and calculate the squared distance from the origin using the formuladistance = x^2 + y^2
, wherex
andy
are the coordinates of the point. We then push the pair[distance, point]
into the max heap. - After processing all points, the max heap will contain the
k
closest points based on their squared distances to the origin. - We extract the
k
closest points from the max heap and store them in theresult
vector. Since we used a max heap, the points with the smallest squared distances (i.e., closest to the origin) will be at the bottom of the heap, so we pop them one by one and store them in theresult
vector.
Time Complexity:
The time complexity of this solution is O(n log k), where n
is the number of points in the input vector points
. The main factor in the time complexity is the insertion and removal operations in the max heap, which have a time complexity of O(log k). We perform these operations for each point in the worst case.
Space Complexity:
The space complexity of this solution is O(k), where k
is the number of points to be returned in the output vector. This is because we use a max heap to store at most k
points based on their squared distances to the origin.