Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 – x2)^2 + (y1 – y2)^2).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
Example 1: Input: points = [[1,3],[-2,2]], k = 1 Output: [[-2,2]] Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]]. Example 2: Input: points = [[3,3],[5,-1],[-2,4]], k = 2 Output: [[3,3],[-2,4]] Explanation: The answer [[-2,4],[3,3]] would also be accepted. |
- Create point object that contains x, y co-ordinates and distance from origin.
- Keep adding points to max heap. Custom comparator that uses distance (inside the point object) as key.
- Make sure size of heap does not go higher than K
- In the end, the K points in the heap are your solution
- Since size of heap capped at k, Time complexity nlogK Time complexity logK
import java.util.*; class Point { int x; int y; double dist; public Point(int x, int y) { this.x = x; this.y = y; this.dist = Math.sqrt(Math.pow(x * 1.0, 2) + Math.pow(y * 1.0, 2)); } } class Solution { public int[][] kClosest(int[][] points, int k) { PriorityQueue maxHeap = new PriorityQueue<Point>((x, y) -> Double.compare(y.dist, x.dist)); for (int i = 0 ; i < points.length ; i++ ) { maxHeap.offer(new Point(points[i][0], points[i][1])); if (maxHeap.size() >= k+1) maxHeap.poll(); } int ret[][] = new int[maxHeap.size()][2]; int i = 0; while (maxHeap.size() > 0) { Point p = (Point) maxHeap.poll(); ret[i][0] = p.x; ret[i][1] = p.y; i++; } return ret; } } |
Skip to content
Just another WordPress site
Just another WordPress site
[Programming Problem] Subsets II
Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets....
[Programming Problem] Flatten Binary Tree to Linked List
Given the root of a binary tree, flatten the tree into a “linked list”: – The “linked list” should use the same TreeNode class...
[Programming Problem] Largest Number
Given a list of non-negative integers nums, arrange them such that they form the largest number and return it. Since the result may...
[Programming Problem] Sum Root to Leaf Numbers
You are given the root of a binary tree containing digits from 0 to 9 only. Each root-to-leaf path in the tree represents...
[Programming Problem] Reverse Linked List II
Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list...
[Programming Problem] Jump Game II
Given an array of non-negative integers nums, you are initially positioned at the first index of the array. Each element in the array represents...
[Programming Problem] Find Minimum in Rotated Sorted Array II
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7]...
[Programming Problem] Find Minimum in Rotated Sorted Array
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7]...
[Programming Problem] Print FooBar Alternately
Suppose you are given the following code: class FooBar { public void foo() { for (int i = 0; i < n; i++) {...
[Programming Problem] The Dining Philosophers
[Problem Link] Solution here is to add some `ordering` on the resources (i.e. forks) requested by the processes (i.e. the philosophers). Identify the resource...