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[2] to represent (x,y) . a[0] is x, a[1] 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.


K closest points quick select

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).

Facebook Interview Question:
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.

Java

JavaScript

Python

Doodle

k closest 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)

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).


Download FindKClosestToCenter.java
Download FindKClosestToCenter.js
Download FindKClosestToCenter.py
Find K closest points to origin (YouTube)

Comments are closed