K Closest Points to Origin

Given an array of points where each point is represented as points[i] = [x_i, y_i] on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance, defined as: 

sqrt( (x₂ – x₁)² + (y₂ – y₁)² )

Note: You can return the k closest points in any order, driver code will sort them before printing.

Examples:

Input: k = 2, points[] = [[1, 3], [-2, 2], [5, 8], [0, 1]]
Output: [[-2, 2], [0, 1]]
Explanation: The Euclidean distances from the origin are:
Point (1, 3) = sqrt(10)
Point (-2, 2) = sqrt(8)
Point (5, 8) = sqrt(89)
Point (0, 1) = sqrt(1)
The two closest points to the origin are [-2, 2] and [0, 1].

Input: k = 1, points = [[2, 4], [-1, -1], [0, 0]]
Output: [[0, 0]]
Explanation: The Euclidean distances from the origin are:
Point (2, 4) = sqrt(20)
Point (-1, -1) = sqrt(2)
Point (0, 0) = sqrt(0)
The closest point to origin is (0, 0).

Constraints:

• 1 <= k <= points.size() <= 10⁵
• -10⁴ <= x_i, y_i <= 10⁴

Approach 01:

#include <vector>
#include <queue>
#include <cmath>

class Solution {
public:
    std::vector<std::vector<int>> kClosest(std::vector<std::vector<int>>& points, int k) {
        // Max heap to store k closest points
        std::priority_queue<std::pair<int, std::pair<int, int>>> maxHeap;
        int totalPoints = points.size();
        
        for (int i = 0; i < totalPoints; i++) {
            int x = points[i][0], y = points[i][1];
            int squaredDistance = (x * x) + (y * y);
            
            // Push the point into the max heap
            maxHeap.push({squaredDistance, {x, y}});
            
            // Maintain only k closest points in the heap
            if (maxHeap.size() > k) {
                maxHeap.pop();
            }
        }
        
        // Extract k closest points
        std::vector<std::vector<int>> closestPoints;
        while (!maxHeap.empty()) {
            closestPoints.push_back({maxHeap.top().second.first, maxHeap.top().second.second});
            maxHeap.pop();
        }
        
        return closestPoints;
    }
};

import heapq

class Solution:
    def kClosest(self, points, k):
        # Max heap to store k closest points
        maxHeap = []
        
        for x, y in points:
            squaredDistance = (x * x) + (y * y)
            
            # Push the point into the max heap (negative distance for max heap behavior)
            heapq.heappush(maxHeap, (-squaredDistance, x, y))
            
            # Maintain only k closest points in the heap
            if len(maxHeap) > k:
                heapq.heappop(maxHeap)
        
        # Extract k closest points
        closestPoints = [[x, y] for _, x, y in maxHeap]
        return closestPoints

Time Complexity:

• Inserting Points into the Heap:

  Each of the \( n \) points is inserted into the heap, taking \( O(\log k) \) time per insertion. This results in \( O(n \log k) \) time.

• Maintaining Heap Size:

  We remove the largest element from the heap whenever its size exceeds \( k \), which takes \( O(\log k) \) per operation.

• Extracting k Closest Points:

  Extracting \( k \) elements from the heap takes \( O(k \log k) \) time.

• Total Time Complexity:

  The overall complexity is \( O(n \log k) \).

Space Complexity:

• Heap Storage:

  We maintain a max heap of size at most \( k \), requiring \( O(k) \) space.

• Output Storage:

  The output vector stores \( k \) points, contributing \( O(k) \) space.

• Total Space Complexity:

  The overall space complexity is \( O(k) \).