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.
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
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | import java.util.*; public class FindKClosestToCenter { //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); } //Solution 2, quick select, 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 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; } //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]); } //Utility print points, Time O(n), Space O(1) private static void printPoints(int[][] points) { for (int i = 0; i < points.length; i++) System.out.print("(" + points[i][0] + ", " + points[i][1] + ") "); System.out.println(); } public static void main(String[] args) throws Exception { int[][] points = { {4,5}, {1,3}, {3,2},{2, 4}, {2, 3},{3,7}}; int k = 2; //Solution 1, Array sorting int[][] res = kClosest(points, k); System.out.println("sorting: "); printPoints(res); //Solution 2, quick select int[][] res1 = kClosestQuick(points, k); System.out.println("quick select: "); printPoints(res1); //Solution 3, Priority Queue int[][] res2 = kClosestPQ(points, k); System.out.println("PriorityQueue: "); printPoints(res2); } } |
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | //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) } //Solution 2, quick select, 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; } //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]); } let points = [[1,3], [3,2], [4, 5], [2, 4], [2, 3], [3, 7]]; let k = 2; //Solution 1, Array sorting let res = kClosest(points, k); console.log("sorting: ") console.log(res); //Solution 2, quick select let res1 = kClosestQuick(points, k); console.log("quick select:") console.log(res1); |
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | import heapq #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, quick select, 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 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] #Compare based on Euclidean distance, Time O(1), Space O(1) def compare(a, b) : return (a[0]*a[0] + a[1]*a[1]) - (b[0]*b[0] + b[1]*b[1]) points = [[1,3], [3,2], [4, 5], [2, 4], [2, 3], [3, 7]] k = 2 #Solution 1, Array sorting res = kClosest(points, k) print("sorting: ") print(res) #Solution 2, quick select res1 = kClosestQuick(points,k) print("quick select: ") print(res1) #Solution 3, Priority Queue res2 = kClosestPQ(points, k) print("priority queue: ") print(res2) |
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)
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.
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)
