Start learning free

LESSON 388 OF 539 · HEAP

K Closest Points to Origin in C#: A Size-k Max-Heap, O(n log k)

Practice O(n log k) Read the full explanation

Given an array of points, where points[i] = [x, y] is a point on the plane, and an integer k, return the k points closest to the origin (0, 0).

The distance between a point [x, y] and the origin is the usual straight-line distance, √(x2 + y2).

Return the points sorted by their distance to the origin, the closest first. Points at the same distance come in order of their x, and points with the same x too in order of their y. The answer is guaranteed to be unique: every point left out is farther from the origin than every point in the answer.

 

Example 1:

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation: [1,3] is √10 away from the origin and [-2,2] is √8 away.
√8 is smaller, so [-2,2] is the closest point.

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: The squared distances are 18, 26 and 20. The two closest points are [3,3] (18) and [-2,4] (20), in that order.

Example 3:

Input: points = [[0,2],[2,0],[1,1],[0,-2],[3,3]], k = 4
Output: [[1,1],[0,-2],[0,2],[2,0]]
Explanation: [1,1] is the closest (√2). [0,2], [2,0] and [0,-2] are all 2 away, so they come by x:
[0,-2] and [0,2] (x = 0) before [2,0], and [0,-2] before [0,2] because -2 < 2. [3,3] is the farthest and is left out.

 

Constraints:

  • 1 <= k <= points.length <= 105
  • -104 <= x, y <= 104
  • The same point can appear more than once.
  • The answer is unique.

Note:

Your algorithm should run in O(n log k) time and use O(k) extra space, where n is the number of points. Sorting all the points by distance would take O(n log n).

No square roots are needed: one point is closer than another exactly when its x2 + y2 is smaller, and that squared distance is a whole number of at most 2 · 108, which fits in a 32-bit integer.

STEP 1 OF 14
    Ctrl + Enter to check

    C# · HEAP

    K Closest Points To Origin in C#, explained

    Problem overview

    The method KClosest receives points, an int[][] where each point is {x, y}, and an int k. It returns the k points closest to the origin, closest first. Points at the same distance are ordered by x, and points with the same x by y. The answer is guaranteed to be unique: every point left out is farther away than every point in the answer.

    For {{3,3},{5,-1},{-2,4}} with k = 2, the squared distances are 18, 26 and 20, so the answer is [[3,3],[-2,4]]. For {{0,2},{2,0},{1,1},{0,-2},{3,3}} with k = 4, the point {1,1} is closest, and {0,2}, {2,0} and {0,-2} are all the same distance away, so they come in order of x: [[1,1],[0,-2],[0,2],[2,0]].

    Approach: keep only the k best so far

    Sorting every point by distance works and costs O(n log n). The lesson asks for O(n log k) time and O(k) extra space, which is better when k is much smaller than n.

    The idea is a max-heap of size k. A heap is a structure that gives quick access to its top element and lets you remove it. In a max-heap the top is the biggest. Go through the points one by one and put each into the heap. If the heap then holds more than k points, remove the top, which is the farthest point in the heap. That point can't be among the k closest, because k other points in the heap are at least as close. After the last point, the heap holds exactly the k closest. Each insertion and removal costs O(log k), because the heap never holds more than k + 1 points.

    No square roots are needed. One point is closer than another exactly when its x * x + y * y is smaller, and with coordinates up to 10,000 in size that sum is at most 200,000,000, which fits in an int.

    A heap is only partly ordered, so after emptying it into a list the code sorts those k entries by distance, then x, then y. That costs O(k log k), which is within the bound.

    Step by step

    1. Create the heap. It is a PriorityQueue<int[], int> named heap: the element is an entry {dist, x, y} and the priority is the distance. C#'s PriorityQueue is a min-heap by default, so the code passes Comparer<int>.Create((a, b) => b - a), which reverses the order and puts the biggest distance on top.
    2. Loop over the points with foreach (int[] point in points). Each point gets one chance to enter the heap.
    3. Read the coordinates: x = point[0] and y = point[1].
    4. Compute the squared distance dist = x * x + y * y.
    5. Add the entry with heap.Enqueue(new int[]{dist, x, y}, dist). The array keeps the point together with its distance, and the second argument is the priority.
    6. Trim: if heap.Count > k, call heap.Dequeue(). It removes the farthest entry, so the heap goes back to k entries.
    7. Empty the heap into a list. Declare closest as a List<int[]> and, while heap.Count > 0, add heap.Dequeue() to it. The entries come out farthest first.
    8. Sort the list with closest.Sort and a comparison of a and b: compare the distances (index 0) if they differ, otherwise the x values (index 1) if they differ, otherwise the y values (index 2).
    9. Build the result. Create int[][] result = new int[k][] and, for i from 0 to k - 1, set result[i] to new int[]{closest[i][1], closest[i][2]}. The answer holds only coordinates, so the distance at index 0 is dropped.
    10. Return result.

    The solution in C#

    class Solution {
    public int[][] KClosest(int[][] points, int k) {
        PriorityQueue<int[], int> heap = new PriorityQueue<int[], int>(Comparer<int>.Create((a, b) => b - a));
        foreach (int[] point in points) {
            int x = point[0], y = point[1];
            int dist = x * x + y * y;
            heap.Enqueue(new int[]{dist, x, y}, dist);
            if (heap.Count > k) {
                heap.Dequeue();
            }
        }
        List<int[]> closest = new List<int[]>();
        while (heap.Count > 0) {
            closest.Add(heap.Dequeue());
        }
        closest.Sort((a, b) => a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] - b[2]);
        int[][] result = new int[k][];
        for (int i = 0; i < k; i++) {
            result[i] = new int[]{closest[i][1], closest[i][2]};
        }
        return result;
    }
}

    The C# details worth knowing:

    • PriorityQueue<TElement, TPriority> is a min-heap. It exists in .NET 6 and later, and Dequeue() returns the element with the smallest priority. Enqueueing "a" with priority 5, "b" with 1 and "c" with 3 dequeues b, c, a. With the reversed comparer it dequeues a, c, b.
    • The element and the priority are separate. Here the element is the array {dist, x, y} and the priority is dist. The heap only compares priorities, which is why the distance is stored twice.
    • The comparer b - a is a shortcut that is safe only because both values are small. For values near the limits of int, the subtraction can overflow and give the wrong sign. b.CompareTo(a) is the general form.
    • The sort comparison uses the same subtraction trick on distances up to 200,000,000 and coordinates of at most 10,000 in size, so it can't overflow here. List<T>.Sort accepts a lambda that returns a negative number, zero or a positive number.
    • Jagged arrays. new int[k][] creates k empty row slots, each null until the loop fills it.
    • Ties in the heap. The heap compares only distances and doesn't keep equal ones in any particular order. The uniqueness guarantee means a tie never decides which points stay.
    • Squares stay in range. A point at {10000, 10000} gives 200,000,000, far below 2,147,483,647. int arithmetic wraps silently on overflow, so with much larger coordinates the sums would have to be long.

    Complexity

    Time: O(n log k). For each of the n points there is one Enqueue and at most one Dequeue on a heap of at most k + 1 entries, each costing O(log k). Emptying the heap and sorting the k survivors adds O(k log k), which is no bigger.

    Space: O(k). The heap holds at most k + 1 entries, and the list and the result hold k each.

    Edge cases and common mistakes

    • k equals the number of points. Nothing is ever removed, and the result is all the points, sorted.
    • Several points at the same distance. The tie-break by x, then y, comes from the final sort, not from the heap.
    • The same point twice. {{1,1},{1,1},{2,2}} with k = 2 returns [[1,1],[1,1]]. The heap holds both copies.
    • Negative coordinates. They are squared, so {-2,2} and {2,-2} are the same distance away.
    • Using a min-heap. The top would be the closest point, not the farthest, so the code would remove the wrong points.
    • Taking a square root. It is unnecessary, and comparing floating-point distances risks wrong ties.
    • Returning the heap's entries directly. They are {dist, x, y}, with the distance first, and they are not sorted.

    Testing

    • {{1,3},{-2,2}} with k = 1 gives [[-2,2]].
    • {{3,3},{5,-1},{-2,4}} with k = 2 gives [[3,3],[-2,4]].
    • {{0,2},{2,0},{1,1},{0,-2},{3,3}} with k = 4 gives [[1,1],[0,-2],[0,2],[2,0]].
    • {{1,1},{1,1},{2,2}} with k = 2 gives [[1,1],[1,1]].
    • {{10000,10000},{-10000,-10000}} with k = 2 gives [[-10000,-10000],[10000,10000]].
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free