Katkat
Back

Find the K Closest Points to the Origin

AsanaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests proficiency with heap-based priority queues and custom sorting logic for spatial coordinates.

Problem Description

You are given a list of points on a 2D plane, where each point is represented as a pair of integers [x, y]. Your goal is to find the k points that are closest to the origin (0, 0).

Rules:

  1. The distance is defined as the squared Euclidean distance: x^2 + y^2.
  2. If two points have the same squared distance, the point with the smaller x coordinate comes first. If the x coordinates are also tied, the point with the smaller y coordinate comes first.
  3. Return the k closest points sorted by distance (and then by the tie-breaking rules defined above).

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

Examples

Example 1: Input: points = [[1, 3], [-2, 2]], k = 1 Output: [[-2, 2]] Explanation: 1^2 + 3^2 = 10, (-2)^2 + 2^2 = 8. Since 8 < 10, [-2, 2] is closer.

Example 2: Input: points = [[0, 1], [1, 0], [0, 0]], k = 2 Output: [[0, 0], [0, 1]] Explanation: Distances are 1, 1, 0. Sorted order: [0, 0] (dist 0), then [0, 1] and [1, 0] (dist 1). Between [0, 1] and [1, 0], [0, 1] is chosen because 0 < 1.

Edge Cases

  • k equals the length of the list (return the whole list sorted).
  • Points with identical coordinates (treat them as distinct entries if they appear as distinct items in the input).

Hints

Hint 1

Consider calculating the squared distance for all points and storing them in a data structure that allows for efficient retrieval of the smallest values.

Hint 2

A Max-Heap of size k can keep track of the closest points seen so far, but ensure your comparison logic handles the tie-breakers correctly.

Hint 3

Alternatively, sorting the entire list using a custom comparator provides a straightforward solution with O(N log N) complexity.

Follow-up questions

  • How would your approach change if the number of points was so large that it could not fit into memory (i.e., streaming data)?
  • Can you optimize the solution to better than O(N log N) time complexity?
  • How would you adapt the solution if the origin point was not (0,0) but an arbitrary coordinate (px, py)?