# Find K closest points to origin (3 solutions) – Time complexity explained

The K closest problem is to find K closest points to the pointer(0,0) (it is called center or origin). The input k is to specify how many points you should return. The Euclidean distance formula is √[ (x2–x1)^2 + (y2–y1)^2]. For this question, we don’t need to calculate the actual distance. To compare two points’ distance to origin, you can simplify the formula to (x2–x1)^2 + (y2–y1)^2. Since the origin is (0,0), it can be further simplified to x^2 + y^2. We can use two-elements array a to represent (x,y) . a is x, a is y.

This post provides 3 solutions: sorting, quickselect and priority queue.

1.The first one is sorting the array by distance. This is the easiest solution. We use sort() method and lambda comparator. The sort() method is provided by built-in library. After sorting, you can return the first k elements. The time complexity of sorting normally is O(nlogn).

2. The second solution uses quickselect. Quickselect is a algorithm to find the kth smallest element in an unordered list. Similar to quicksort, it chooses one element as a pivot and partition data based on the pivot. This reduces the time complexity from O(nlogn) to average O(n). This solution has best performance but it is relatively difficult to implement. 3.The last one uses PriorityQueue. ProrityQueue is data structures commonly used to solve find kth problem. There are built in PrirorityQueue in Java and Python. In Java, we use the PriorityQueue class. In Python, we use heapq. Javascript does not have a standard priority queue data structure that you can use out of the box. The time complexity is O(nlogn).

You are given n points (x1, y1), (x2, y2), ….. (xn, yn) of a two-dimensional graph. Find ‘k’ closest points to (0,0) . Euclidean distance can be used to find the distance between 2 points.

## Doodle Output:
sorting:
(1, 3) (3, 2)
quick select:
(1, 3) (3, 2)
PriorityQueue:
(1, 3) (3, 2)

O Notation:
1. Array sorting:
Time complexity: O(nlogn), Space complexity: O(n)
2. Quickselect:
Time complexity: O(n), Space complexity: O(logn)
3. PriorityQueue:
Time complexity: O(n*logn), Space complexity: O(n)

How to find k closest points to origin?

There are 3 solutions: sorting, quickselect and priority queue. Using sort() method and priority queue data structure are easy to implement. But the time complexity is not as good as quickselect. Quickselect is a algorithm to use divide and conquer to find the kth smallest element in an unordered list.

What is the best time complexity to find K closest points to origin?

The best time complexity of find k closest points to origin is O(n). The solution is quickselect. Similar to quicksort, quickselect chooses one element as a pivot and partitions data based on the pivot. It reduces the time complexity of find kth problem from O(nlogn) to average O(n).