K Closest Points to Origin

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.

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:

1. The kClosest function takes a reference to a vector of vectors points and an integer k.
2. 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 exceeds k.
3. We iterate through each point in the points vector and calculate the squared distance from the origin using the formula distance = x^2 + y^2, where x and y are the coordinates of the point. We then push the pair [distance, point] into the max heap.
4. After processing all points, the max heap will contain the k closest points based on their squared distances to the origin.
5. We extract the k closest points from the max heap and store them in the result 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 the result 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.