973. K Closest Points to Origin

📝 Problem Details

• Title: 973. K Closest Points to Origin
• Link: https://leetcode.com/problems/k-closest-points-to-origin/
• Difficulty: Medium
• Tags/Categories: Priority-Queue

input array points where points[i] = [x,y] representing a point in a coordinate plane input integer k return the k closet points to the origin [0,0] calculate distance by using Euclidean Distance formula sqrt( (x1, x2)^2 + (y1, y2)^2 )

💭What Were My Initial Thoughts?

- use a max-heap of fixed size k to maintain the k closest points to the origin
- can potentially use a helper function to calculate the euclidean distance since we know x1,y1 are always going to be 0,0 
- the max-heap should contain pairs, where the key is the distance and the value is the points
- after going through all points convert the priority 

💡 Explanation of Solution

1. Use a priority-queue of fixed size k
	- store points in the heap as {distance, (x,y)}

2. calculate squared euclidean distance (avoid using sqrt for efficiency)
3. iterate through all points:
	- push each point into the heap
	- if heap size exceeds k, remove the farthest point
4. convert heap to a vector and return 

⌛ Complexity Analysis

Time Complexity: O(n log k) for heap operations
Space Complexity: O(k) for the storage of k elements in the heap and conversion to a results vector

💻 Implementation of Solution

class Solution {
public:
    // Helper function to calculate the Euclidean distance from (0,0)
    double euclideanDistance(int x, int y) {
        return sqrt((x - 0) * (x - 0) + (y - 0) * (y - 0)); // Explicit formula
    }
 
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        // Max-heap (priority queue) of size K
        priority_queue<pair<double, vector<int>>> maxHeap;
 
        // Iterate through all points
        for (const auto& point : points) {
            int x = point[0], y = point[1];
 
            // Calculate Euclidean distance explicitly
            double dist = euclideanDistance(x, y);
 
            // Push {distance, point} into max-heap
            maxHeap.push({dist, point});
 
            // If heap size exceeds k, remove the farthest point
            if (maxHeap.size() > k) {
                maxHeap.pop();
            }
        }
 
        // Extract k closest points from heap
        vector<vector<int>> result;
        while (!maxHeap.empty()) {
            result.push_back(maxHeap.top().second);
            maxHeap.pop();
        }
 
        return result;
    }
};