973. K Closest Points to Origin

At a Glance

Topic: Array
Pattern: Analyze Pattern
Difficulty: Medium
LeetCode: 973

Problem Statement

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Example 1:

Input: points = [[1,3],[-2,2]], k = 1 Output: [[-2,2]] Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], k = 2 Output: [[3,3],[-2,4]] Explanation: The answer [[-2,4],[3,3]] would also be accepted.

Constraints:

1 <= k <= points.length <= 104
-104 <= xi, yi <= 104

Approach & Solution Steps

Brute force — compute distances, sort — O(n log n) time.
Better — max-heap of size k over distance — O(n log k) time, O(k) space.
Optimal — same heap approach or average O(n) quickselect on squared distance — heap solution is interview-stable.

Optimal JS Solution

class MaxHeap {
  constructor(compare) {
    this.data = [];
    this.compare = compare;
  }

  size() {
    return this.data.length;
  }

  push(item) {
    this.data.push(item);
    this.bubbleUp(this.data.length - 1);
  }

  pop() {
    if (this.data.length === 0) {
      return undefined;
    }
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      this.bubbleDown(0);
    }
    return top;
  }

  peek() {
    return this.data[0];
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.compare(this.data[index], this.data[parentIndex]) <= 0) {
        break;
      }
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  bubbleDown(index) {
    const length = this.data.length;
    while (true) {
      const leftChild = index * 2 + 1;
      const rightChild = index * 2 + 2;
      let candidate = index;
      if (
        leftChild < length &&
        this.compare(this.data[leftChild], this.data[candidate]) > 0
      ) {
        candidate = leftChild;
      }
      if (
        rightChild < length &&
        this.compare(this.data[rightChild], this.data[candidate]) > 0
      ) {
        candidate = rightChild;
      }
      if (candidate === index) {
        break;
      }
      this.swap(index, candidate);
      index = candidate;
    }
  }

  swap(leftIndex, rightIndex) {
    const temp = this.data[leftIndex];
    this.data[leftIndex] = this.data[rightIndex];
    this.data[rightIndex] = temp;
  }
}

function kClosest(points, k) {
  const distSq = (point) => point[0] * point[0] + point[1] * point[1];
  const heap = new MaxHeap((leftPoint, rightPoint) =>
    distSq(leftPoint) - distSq(rightPoint)
  );
  for (const point of points) {
    heap.push(point);
    if (heap.size() > k) {
      heap.pop();
    }
  }
  return heap.data;
}

Edge Cases & Pitfalls

Always consider empty or null inputs.
Watch out for off-by-one index errors.