Find K closest points to origin (3 solutions) – code

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 represent the point as a class with attributes x and y. Or we can use two-elements array a[2]. x can be represented as a[0], y can be represented as a[1]. The second is what we use here.

This post provides 3 solutions. The first one is sorting the array by distance. The time complexity of sorting normally is O(nlogn). It is an intuitive solution.

The second solution uses quickselect. Quickselect is an algorithm designed to solve kth smallest problem efficiently. It might take more time to implement in the interview. But it has better time and space complexity when you are asked to optimize.


K closest points quick select

The last one uses PriorityQueue. ProrityQueue is data structures commonly used to solve find kth problem. You must define a customized comparator before you add elements to PriorityQueue. You can use the library of PriorityQueue provided by the language you use. Or you can implement it on your own.

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

Solution 1: Array sorting

Using array sorting is the most intuitive way. Most programing languages provide sort() method in the library. You can also make your own sorting methods. Here we use the sort() from Java, JavaScript and Python built-in library respectively. The time complexity depends on how the method is developed in the language. O(nlogn) is a good bet.

Java

JavaScript

Python

Solution 2: Quickselect

Quickselect is a algorithm to find the kth smallest element in an unordered list. It uses the same overall approach as quicksort, choosing one element as a pivot and partition data based on the pivot. This reduces the time complexity from O(nlogn) to average O(n).

Java

JavaScript

Python

Doodle

k closest points doodle

Solution 3: Priority queue

Priority queue is partially ordered queue. You can create your own priority queue class or use the built-in library provided by the languages. Here we use the PriorityQueue class from Java, heapq from python. Javascript does not have a standard priority queue data structure that you can use out of the box. We skip here. Normally to add element in priority queue is O(logn). So the overall time complexity is O(nlogn).

Java

Python

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

O Notation:
Array sorting:
Time complexity: O(nlogn)
Space O(n)

Quickselect:
Time complexity: O(n)
Space complexity: O(1)

PriorityQueue:
Time complexity: O(n*logn)
Space complexity: O(n)

Note:
If you have any questions or want to put comments, please post at youtube. I will answer you!

Download FindKClosestPointsToCenter.java
Find K closest points to origin (YouTube)

Comments are closed