Find the K Closest Points to the Origin

Question

The question asks the candidate to implement an algorithm that finds the K closest points to the origin from a given list of points in a 2D space.

Codemia · Accepted Answer

To find the K closest points to the origin, we can use a priority queue (min-heap) to efficiently retrieve the closest points. The distance from the origin can be calculated using the Euclidean distance formula. We will iterate through the list of points, calculate their distances, and maintain a heap of size K to store the closest points.

1. Initialize a min-heap.
2. For each point in the list, calculate the distance from the origin.
3. Push the point and its distance into the heap.
4. If the heap exceeds size K, pop the farthest point.
5. After processing all points, the heap will contain the K closest points.

The time complexity of this approach is O(N log K), where N is the number of points. This is due to the insertion and removal operations in the heap. The space complexity is O(K) for storing the K closest points.

```python
import heapq

def k_closest(points, K):
    min_heap = []
    for (x, y) in points:
        distance = x**2 + y**2  # Using squared distance for efficiency
        heapq.heappush(min_heap, (distance, (x, y)))
        if len(min_heap) > K:
            heapq.heappop(min_heap)
    return [point for (_, point) in min_heap]
```

It's important to consider edge cases such as when K is greater than the number of points or when the list of points is empty. In such cases, we should return an empty list or handle it gracefully.

Find the K Closest Points to the Origin

Asana

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Asana Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string