Katkat
Back

Find K Nearest Points

SnapchatMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This question tests the ability to efficiently find the k-closest points to an origin in a 2D plane, focusing on heap-based or selection-based data structures.

Problem Statement

Given a list of points on a 2D plane represented as [x, y] coordinates, write a function that returns the k points closest to the origin (0, 0). The distance between two points (x1, y1) and (x2, y2) is the standard Euclidean distance: sqrt((x1 - x2)^2 + (y1 - y2)^2). Since we are comparing distances, you may compare the squared Euclidean distances x^2 + y^2 to avoid unnecessary square root operations.

Function Signature

def k_closest(points: list[list[int]], k: int) -> list[list[int]]:

Constraints

  • 1 <= k <= len(points) <= 10^5
  • -10^4 <= x, y <= 10^4

Example 1

Input: points = [[1, 3], [-2, 2]], k = 1 Output: [[-2, 2]] Explanation: The squared distance of [1, 3] is 10. The squared distance of [-2, 2] is 8. Since 8 < 10, [-2, 2] is closer.

Example 2

Input: points = [[3, 3], [5, -1], [-2, 4]], k = 2 Output: [[3, 3], [-2, 4]] Explanation: Squared distances are 18, 26, and 20 respectively. The two smallest are 18 and 20.

Edge Cases

  • k equals the total number of points.
  • All points have the same distance to the origin.
  • Points with negative coordinates or zero coordinates.

Hints

Hint 1

Instead of calculating the actual distance, work with the squared distance `x^2 + y^2` to keep computations in integer space.

Hint 2

Consider using a Max-Heap of size `k` to keep track of the `k` smallest elements encountered so far while iterating through the points.

Hint 3

For an O(n) average time complexity approach, consider the QuickSelect algorithm, which partitions the array around a pivot to find the k-th smallest element.

Follow-up questions

  • How would you modify your solution if the points were stored in a massive, read-only file that does not fit into memory?
  • If the points were updated frequently (e.g., streaming data), what data structure would you use to maintain the k-closest points efficiently?
  • How does the time complexity change if you use a full sorting approach versus a heap-based approach?