Is K Closest Points to Origin easy or hard?

K Closest Points to Origin is typically rated Medium difficulty. The basic idea of comparing squared distances is straightforward, but the challenge is choosing the right algorithm. Interviewers often expect candidates to move beyond sorting and discuss heap or Quickselect optimizations.

How to solve K Closest Points to Origin in O(n)?

Use the Quickselect algorithm. Compute squared distances and apply a partition step similar to quicksort so points with smaller distances move left of the pivot. Recursively process only the side containing the k-th element. Once the pivot index reaches k, the first k elements represent the closest points in average O(n) time.

What is the best approach for K Closest Points to Origin?

Quickselect is the optimal algorithm with average O(n) time because it partially partitions the array until the k closest points are placed in the first k positions. In practice, many engineers prefer a max-heap solution with O(n log k) complexity because it is easier to implement and performs well when k is much smaller than n.

What data structure is used in K Closest Points to Origin?

The most common data structure is a max-heap (priority queue) that stores the k closest points seen so far. Each heap entry tracks the squared distance and the point itself. Quickselect solutions instead rely on array partitioning rather than an additional data structure.

What is the time complexity of K Closest Points to Origin?

The complexity depends on the approach used. Sorting all points takes O(n log n). Using a max-heap of size k takes O(n log k). Quickselect improves this to average O(n) time because it avoids sorting the entire array and only partitions around the k-th smallest distance.

K Closest Points to Origin Python or Java solution approach?

Python and Java solutions usually compute squared distances and either sort the array or maintain a max-heap of size k. Python often uses heapq while Java uses PriorityQueue with a custom comparator. Both implementations achieve O(n log k) time with O(k) extra space using the heap method.

Is K Closest Points to Origin asked at Google, Amazon, or Meta?

K Closest Points to Origin frequently appears in interviews at companies such as Amazon, Google, and Meta. It tests knowledge of heaps, partition-based selection, and distance calculations on geometric points. Interviewers often expect candidates to discuss both heap and Quickselect approaches.

Description Solution Video 9:29

973. K Closest Points to Origin

Medium69.4% acceptance17 companies

Given an array of points where points[i] = [x_i, y_i] 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., √(x₁ - x₂)² + (y₁ - y₂)²).

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 <= 10⁴
-10⁴ <= x_i, y_i <= 10⁴

Asked at 17 companies

Asana Plaid Wix Meta Swiggy Whatnot Amazon Snapchat Axon

Google Salesforce Microsoft

+5 more

Bloomberg Oracle Apple Goldman Sachs LinkedIn

Topics

9:29

Still stuck?Read 5 approaches, or watch a walkthrough.

Open solution

973. K Closest Points to Origin

Asked at 17 companies

Topics

Similar problems