K closest points to center | 3 solutions

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.

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

	//Solution 1, Array sorting, Time worst O(n^2), average O(n), Space O(n), n is number of points
	public static int[][] kClosest(int[][] points, int k) {
		Arrays.sort(points, (a, b) -&gt; compare(a, b));
		return Arrays.copyOfRange(points, 0, k);
	}

	//Compare based on Euclidean distance formula, Time O(1), Space O(1)
	private static int compare(int[] a, int[] b) {
	    return (a[0]*a[0] + a[1]*a[1]) - (b[0]*b[0] + b[1]*b[1]);
	}

//Solution 1, Array sorting, Time worst O(n^2), average O(n), Space O(n), n is number of points

public static int[][] kClosest(int[][] points, int k) {

Arrays.sort(points, (a, b) -> compare(a, b));

return Arrays.copyOfRange(points, 0, k);

}

//Compare based on Euclidean distance formula, Time O(1), Space O(1)

private static int compare(int[] a, int[] b) {

return (a[0]*a[0] + a[1]*a[1]) - (b[0]*b[0] + b[1]*b[1]);

}

JavaScript

//solution 1: use sorting, Time worst O(n^2) average O(nlogn), Space O(n)
function kClosest (points , k)  {
    const sorted = points.sort((a, b) =&gt; compare(a,b))
    return sorted.slice(0, k)
}

//Compare based on Euclidean distance, Time O(1), Space O(1)
function compare(a, b) {
    return (a[0]*a[0] + a[1]*a[1]) - (b[0]*b[0] + b[1]*b[1]);
}

//solution 1: use sorting, Time worst O(n^2) average O(nlogn), Space O(n)

function kClosest (points , k) {

const sorted = points.sort((a, b) => compare(a,b))

return sorted.slice(0, k)

}

//Compare based on Euclidean distance, Time O(1), Space O(1)

function compare(a, b) {

return (a[0]*a[0] + a[1]*a[1]) - (b[0]*b[0] + b[1]*b[1]);

}

Python

#Solution 1: array sorting, Time worst O(n^2) average O(nlogn), Space O(n)
def kClosest(points, k):
    points.sort(key = lambda p: p[0]*p[0] + p[1]*p[1])
    return points[:k]

#Solution 1: array sorting, Time worst O(n^2) average O(nlogn), Space O(n)

def kClosest(points, k):

points.sort(key = lambda p: p[0]*p[0] + p[1]*p[1])

return points[:k]

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

	//Solution 2, quickselect, Time worst O(n^2) average O(n), Space worst O(n) average O(logn)
	public static int[][] kClosestQuick(int[][] points, int k) {
	     int n =  points.length, low = 0, high = n - 1;
	     while (low <= high) {
	    	 int mid = partition(points, low, high);
	    	 if (mid == k) 
	    		 break;
	    	 if (mid < k) 
	        	low = mid + 1; 
	    	 else 
	            high = mid - 1;
	    }
	    return Arrays.copyOfRange(points, 0, k);
	}

	//Partition, two pointers, Time worst O(n^2) average O(n), Space O(1)
	private static int partition(int[][] points, int low, int high) {
	    int[] pivot = points[low];
	    while (low < high) {
	        while (low < high && compare(points[high], pivot) >= 0) {
	        	high--;
	        }
	        points[low] = points[high];	        
	        while (low < high && compare(points[low], pivot) <= 0){ 
	        	low++;
	        }
	        points[high] = points[low];
	    }    
	    points[low] = pivot;	    
	    return high;
	}

//Solution 2, quickselect, Time worst O(n^2) average O(n), Space worst O(n) average O(logn)

public static int[][] kClosestQuick(int[][] points, int k) {

int n = points.length, low = 0, high = n - 1;

while (low <= high) {

int mid = partition(points, low, high);

if (mid == k)

break;

if (mid < k)

low = mid + 1;

else

high = mid - 1;

}

return Arrays.copyOfRange(points, 0, k);

}

//Partition, two pointers, Time worst O(n^2) average O(n), Space O(1)

private static int partition(int[][] points, int low, int high) {

int[] pivot = points[low];

while (low < high) {

while (low < high && compare(points[high], pivot) >= 0) {

high--;

}

points[low] = points[high];

while (low < high && compare(points[low], pivot) <= 0){

low++;

}

points[high] = points[low];

}

points[low] = pivot;

return high;

}

JavaScript

//Solution 2, quickselect, Time worst O(n^2) average O(n), Space worst O(n) average O(logn)
function kClosestQuick(points, k) {
    var n =  points.length, low = 0, high = n - 1;
    while (low <= high) {
        let mid = partition(points, low, high);
        if (mid == k) 
            break;
        if (mid < k) 
            low = mid + 1; 
        else 
            high = mid - 1;
    }
    return points.slice(0, k)
}

//Partition, Time worst O(n^2) average O(n), Space O(1)
function partition(points, low, high) {
    var pivot = points[low];
    while (low < high) {
        while (low < high && compare(points[high], pivot) >= 0) 
            high--;
        points[low] = points[high];
        while (low < high && compare(points[low], pivot) <= 0) 
            low++;
        points[high] = points[low];
    }
    points[low] = pivot;
    return low;
}

//Solution 2, quickselect, Time worst O(n^2) average O(n), Space worst O(n) average O(logn)

function kClosestQuick(points, k) {

var n = points.length, low = 0, high = n - 1;

while (low <= high) {

let mid = partition(points, low, high);

if (mid == k)

break;

if (mid < k)

low = mid + 1;

else

high = mid - 1;

}

return points.slice(0, k)

}

//Partition, Time worst O(n^2) average O(n), Space O(1)

function partition(points, low, high) {

var pivot = points[low];

while (low < high) {

while (low < high && compare(points[high], pivot) >= 0)

high--;

points[low] = points[high];

while (low < high && compare(points[low], pivot) <= 0)

low++;

points[high] = points[low];

}

points[low] = pivot;

return low;

}

Python

#Solution 2, quickselect, Time worst O(n^2) average O(n), Space worst O(n) average O(logn)
def kClosestQuick(points, k) :
    n =  len(points)
    low = 0
    high = n - 1
    while (low <= high) :
        mid = partition(points, low, high)
        if mid == k:
            break
        if (mid < k): 
            low = mid + 1 
        else :
            high = mid - 1
    return points[:k]

#Partition, Time worst O(n^2) average O(n), Space O(1)
def partition(points, low, high) :
    pivot = points[low]
    while (low < high) :
        while low < high and compare(points[high], pivot) >= 0: 
            high -= 1
        points[low] = points[high]
        while low < high and compare(points[low], pivot) <= 0: 
            low += 1
        points[high] = points[low]
    points[low] = pivot
    return low

#Solution 2, quickselect, Time worst O(n^2) average O(n), Space worst O(n) average O(logn)

def kClosestQuick(points, k) :

n = len(points)

low = 0

high = n - 1

while (low <= high) :

mid = partition(points, low, high)

if mid == k:

break

if (mid < k):

low = mid + 1

else :

high = mid - 1

return points[:k]

#Partition, Time worst O(n^2) average O(n), Space O(1)

def partition(points, low, high) :

pivot = points[low]

while (low < high) :

while low < high and compare(points[high], pivot) >= 0:

high -= 1

points[low] = points[high]

while low < high and compare(points[low], pivot) <= 0:

low += 1

points[high] = points[low]

points[low] = pivot

return low

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

	//Solution 3, PriorityQueue, Time O(nlogn), space O(n)
	public static int[][] kClosestPQ(int[][] points, int k) {
	    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> compare(a, b)); //sort by distance, ascending 
	    for (int[] p : points) 
	        pq.add(p);    
	    int[][] res = new int[k][2];
	    for (int i = 0; i < k; i++)
	    	res[i] = pq.poll();
	    return res;
	}

//Solution 3, PriorityQueue, Time O(nlogn), space O(n)

public static int[][] kClosestPQ(int[][] points, int k) {

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> compare(a, b)); //sort by distance, ascending

for (int[] p : points)

pq.add(p);

int[][] res = new int[k][2];

for (int i = 0; i < k; i++)

res[i] = pq.poll();

return res;

}

Python

import heapq

#Solution 3: Priorty queue, Time O(nlogn), Space O(n), n is number of points 
def kClosestPQ(points, k):
    pq = []
    for p in points:
        dist = p[0]*p[0] + p[1]*p[1]
        heapq.heappush(pq, (-dist, p))
        if len(pq) &gt; k:
            heapq.heappop(pq)     
    return [point[1] for point in pq]

import heapq

#Solution 3: Priorty queue, Time O(nlogn), Space O(n), n is number of points

def kClosestPQ(points, k):

pq = []

for p in points:

dist = p[0]*p[0] + p[1]*p[1]

heapq.heappush(pq, (-dist, p))

if len(pq) > k:

heapq.heappop(pq)

return [point[1] for point in pq]

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)

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

Java

JavaScript

Python

Java

JavaScript

Python

Doodle

Java

Python

Related

Recent Posts

Categories

Java coding book

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

Java

JavaScript

Python

Java

JavaScript

Python

Doodle

Java

Python

Share this:

Related

Recent Posts

Categories

Java coding book