Editorial: K Closest Points to Origin

1 Intuition

We can sort points by their distance from origin, then return the first k points. Alternatively, use a max heap to maintain k closest points. Both approaches are efficient.

2 Approach

**Method 1 (Sorting):** 1. Calculate distance for each point 2. Sort by distance 3. Return first k points **Method 2 (Heap):** 1. Use max heap of size k 2. Add distances, keep smallest k 3. Return k points from heap

3 Complexity Analysis

**Time Complexity (Sorting):** O(n log n) **Time Complexity (Heap):** O(n log k) **Space Complexity:** O(k) for heap approach Heap approach is better when k << n.

4 Solution Code

def kClosest(points, k):
        # Method 1: Using sorting
        points.sort(key=lambda p: p[0]**2 + p[1]**2)
        return points[:k]

        # Method 2: Using heap (better for large n, small k)
        import heapq
        return heapq.nsmallest(k, points, key=lambda p: p[0]**2 + p[1]**2)

vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    sort(points.begin(), points.end(), [](auto& a, auto& b) {
        return a[0]*a[0] + a[1]*a[1] < b[0]*b[0] + b[1]*b[1];
    });
    return vector<vector<int>>(points.begin(), points.begin() + k);
}

5 Code Walkthrough

For points=[[1,3],[-2,2]], k=1: - Distance (1,3): √(1²+3²)=√10≈3.16 - Distance (-2,2): √(4+4)=√8≈2.83 - √8 < √10, so (-2,2) is closest Result: [[-2,2]]