Katkat
Back

Return the K Closest Points with Deterministic Ties

AsanaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests the ability to efficiently find the nearest neighbors to a target coordinate while maintaining a deterministic ordering for ties, ensuring reproducible results.

Problem Statement

Given a list of 2D coordinates points (represented as [x, y] pairs) and a target coordinate [tx, ty], return the k points that are closest to the target.

Distance is defined as the Euclidean distance. If two points have the same distance to the target, the point with the smaller x coordinate should be considered "closer." If both the distance and the x coordinates are equal, the point with the smaller y coordinate is considered "closer."

Implement the function: def k_closest(points: list[list[int]], target: list[int], k: int) -> list[list[int]]:

Constraints

  • 1 <= k <= len(points) <= 10^5
  • Coordinates are integers between -10^4 and 10^4
  • The output must be sorted by distance (ascending), then by x (ascending), then by y (ascending).

Examples

Example 1: Input: points = [[1, 3], [-2, 2]], target = [0, 0], k = 1 Output: [[-2, 2]] Explanation: Distance to [0,0] for [1, 3] is sqrt(10), for [-2, 2] is sqrt(8). [-2, 2] is closer.

Example 2: Input: points = [[1, 1], [1, -1]], target = [0, 0], k = 1 Output: [[1, -1]] Explanation: Both have distance sqrt(2). Since x-coordinates are equal (1=1), we compare y-coordinates. -1 < 1, so [1, -1] is chosen.

Edge Cases

  • k equals the length of points.
  • points contains the target itself (distance is 0).

Hints

Hint 1

Instead of calculating the actual Euclidean distance (which involves square roots and floats), use the squared distance `(x1-x2)^2 + (y1-y2)^2` to maintain precision.

Hint 2

Consider using a min-heap to keep track of the `k` closest points, or a sorting approach if the constraints allow.

Hint 3

To handle ties deterministically, create a custom comparison key that returns a tuple: `(squared_distance, x, y)`.

Follow-up questions

  • How would your solution change if you needed to return the k closest points in an online stream where you don't know the total number of points in advance?
  • What is the time complexity of your approach if you use a heap versus full sorting?
  • How would you optimize the search if the points were stored in a spatial index, such as a K-D Tree?