973. K Closest Points to Origin

MediumView on LeetCode

Array Math Divide and Conquer Sorting Heap (Priority Queue)quickselect Geometry

Time: O(n log k)

Space: O(k)

Intuition

Find k points with smallest Euclidean distance. Max-heap of size k or QuickSelect.

Algorithm

1Max-heap size k: for each point compute x^2+y^2. Push, pop if size > k.
2Remaining points in heap are the k closest.

Common Pitfalls

•Compare squared distances to avoid sqrt. QuickSelect gives O(n) average.

973.cs

// Approach: Max-heap of size k; maintain the k smallest squared distances by evicting the farthest when size exceeds k.
// Time: O(n log k) Space: O(k)

public class Solution
{
    public int[][] KClosest(int[][] points, int k)
    {
        int[][] ans = new int[k][];
        var maxHeap = new PriorityQueue<int[], int[]>(Comparer<int[]>.Create((a, b) => SquareDist(b).CompareTo(SquareDist(a))));

        foreach (int[] point in points)
        {
            maxHeap.Enqueue(point, point);
            if (maxHeap.Count > k)
                maxHeap.Dequeue();
        }

        for (int i = k - 1; i >= 0; i--)
            ans[i] = maxHeap.Dequeue();

        return ans;
    }

    private int SquareDist(int[] p)
    {
        return p[0] * p[0] + p[1] * p[1];
    }
}

Was this solution helpful?