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
|
1 2 3 4 5 6 7 8 9 10 |
//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
|
1 2 3 4 5 6 7 8 9 10 |
//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
|
1 2 3 4 |
#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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
//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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
//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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#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
|
1 2 3 4 5 6 7 8 9 10 |
//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
|
1 2 3 4 5 6 7 8 9 10 11 |
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)
