DDSA Solutions

973. K Closest Points to Origin

MediumView on LeetCode
ArrayMathDivide and ConquerSortingHeap (Priority Queue)quickselectGeometry
Time: O(n log k)
Space: O(k)

Problem Overview

Find k points with smallest Euclidean distance.

Intuition

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

Algorithm

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

Common Pitfalls

  • •Compare squared distances to avoid sqrt. QuickSelect gives O(n) average.
973.cs
C#
// 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?

Related Problems