Start learning free

LESSON 389 OF 540 · HEAP

K Closest Points to Origin in TypeScript: Max-Heap of Size 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 10
    Ctrl + Enter to check

    TYPESCRIPT · HEAP

    K Closest Points To Origin in TypeScript, explained

    Problem overview

    The method kClosest(points, k) receives an array of points, where each point is [x, y], and a number k. It returns the k points closest to the origin (0, 0), sorted by distance with the closest first. Points at the same distance are ordered by x, and then by y. The answer is unique: every point left out is farther away than every point in the answer.

    For points = [[1, 3], [-2, 2]] and k = 1, the point [1, 3] is √10 from the origin and [-2, 2] is √8, so the answer is [[-2, 2]]. For [[0, 2], [2, 0], [1, 1], [0, -2], [3, 3]] with k = 4, the point [1, 1] comes first; [0, 2], [2, 0] and [0, -2] are all at distance 2, so they are ordered by x and then y; [3, 3] is left out. The answer is [[1, 1], [0, -2], [0, 2], [2, 0]].

    The budget is O(n log k) time and O(k) extra space, where n is the number of points. Sorting every point by distance would take O(n log n).

    Approach: keep the k best in a max-heap

    Two ideas make this efficient.

    Compare squared distances. A point is closer than another exactly when its x * x + y * y is smaller, so no square root is needed. With coordinates up to 10,000 in size, the squared distance is a whole number of at most 200,000,000, which a TypeScript number holds exactly.

    Keep only the best k so far. Use a max-heap, a structure whose top is always the biggest entry, ordered by distance. Insert each point. If the heap then holds more than k points, remove the top: it is the farthest of the k + 1 points, so it can't be among the k closest. After every point the heap holds the k closest points seen so far. Each insert and each removal costs O(log k) because the heap never has more than k + 1 entries, so the whole pass is O(n log k).

    A heap is only partly ordered, so at the end the points are taken out and sorted. That final sort has just k items, costing O(k log k), which is within the budget because k is at most n.

    The lesson provides a ready-to-use MaxHeap class. You create it with a compare function that works like the one in sort, and it offers insert(value), extract(), peek(), size() and isEmpty(). extract() removes the top and returns it.

    Step by step

    1. Create the heap with new MaxHeap((a, b) => a[0] - b[0]). Each entry will be [dist, x, y], and the compare function orders entries by dist, so the farthest point stays on top.
    2. Visit every point with for (const [x, y] of points). The brackets take each point apart into x and y; this is destructuring.
    3. Compute dist as x * x + y * y.
    4. Insert [dist, x, y]. The entry keeps the point together with the number the heap orders by.
    5. Trim the heap: if heap.size() > k, call heap.extract() to drop the farthest entry.
    6. Prepare the output with closest, an empty number[][].
    7. Drain the heap with a while loop that runs while !heap.isEmpty(). It takes k turns.
    8. Push each extracted entry onto closest. The entries come out from the farthest to the closest.
    9. Sort closest with (a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]. When two distances are equal, a[0] - b[0] is 0, which counts as false, so || moves on to compare x and then y.
    10. Return the points without their distances with closest.map, taking each entry apart as [dist, x, y] and returning [x, y].

    The solution in TypeScript

    class Solution {
    kClosest(points: number[][], k: number): number[][] {
        const heap = new MaxHeap((a, b) => a[0] - b[0]);
        for (const [x, y] of points) {
            const dist = x * x + y * y;
            heap.insert([dist, x, y]);
            if (heap.size() > k) {
                heap.extract();
            }
        }
        const closest: number[][] = [];
        while (!heap.isEmpty()) {
            closest.push(heap.extract());
        }
        closest.sort((a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]);
        return closest.map(([dist, x, y]) => [x, y]);
    }
}

    TypeScript details worth knowing

    The compare function. a[0] - b[0] is negative when a is smaller, zero when they are equal and positive when a is bigger. Subtraction works as a comparison here because the distances are whole numbers far below the point where doubles lose precision. A max-heap keeps the biggest entry by this ordering on top.

    Sorting needs a comparator. sort() without one compares elements as strings, which would put 10 before 9, and arrays would be turned into text. The comparator gives a numeric ordering, and sort changes the array in place.

    The || chain. 0 is falsy, so a[0] - b[0] || a[1] - b[1] is the distance difference when it isn't 0 and the x difference when it is. Adding || a[2] - b[2] breaks remaining ties by y.

    Destructuring. const [x, y] of points and ([dist, x, y]) => [x, y] are the same idea: the left side takes an array apart into named variables. In the final map the variable dist is named only to skip over the first element; it isn't used.

    Types such as number[][] are checked by the compiler and erased when it produces JavaScript.

    Complexity

    Time: O(n log k). Every point costs one insert and sometimes one removal in a heap of at most k + 1 entries, each O(log k). Draining the heap and sorting the k survivors adds O(k log k), which doesn't exceed the first part because k <= n.

    Space: O(k). The heap and the closest array each hold at most k + 1 entries, besides the returned answer of k points.

    Edge cases and common mistakes

    • k equals the number of points. Nothing is ever removed, and the answer is every point sorted by distance, then x, then y.
    • Duplicate points. The same point can appear more than once. [[1, 1], [1, 1], [2, 2]] with k = 2 returns [[1, 1], [1, 1]].
    • The origin itself. [[0, 0]] has distance 0 and is returned as is.
    • Using a min-heap by mistake. A min-heap would drop the closest point when the heap grows past k, which keeps the wrong ones. The top must be the farthest.
    • Trimming at the wrong size. Remove only when the size is greater than k, so that exactly k points remain.
    • Skipping the final sort. The heap gives the points from farthest to closest at best, and equal distances aren't in x and y order, so the sort is still needed.
    • Taking square roots. They add nothing: the order of squared distances is the same, and whole numbers compare exactly.

    Testing

    The lesson's code gives these results:

    kClosest([[1,3],[-2,2]], 1)                      -> [[-2,2]]
kClosest([[3,3],[5,-1],[-2,4]], 2)               -> [[3,3],[-2,4]]
kClosest([[0,2],[2,0],[1,1],[0,-2],[3,3]], 4)    -> [[1,1],[0,-2],[0,2],[2,0]]
kClosest([[1,1],[1,1],[2,2]], 2)                 -> [[1,1],[1,1]]
kClosest([[0,0]], 1)                             -> [[0,0]]

    The same point can repeat, but two different points at the same distance must not compete for the last place: the answer is always unique.

    Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free