We have a list of points on the plane. Find the K closest points to the origin (0, 0).
(Here, the distance between two points on a plane is the Euclidean distance.)
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]] (The answer [[-2,4],[3,3]] would also be accepted.)
Note:
1 <= K <= points.length <= 10000-10000 < points[i][0] < 10000-10000 < points[i][1] < 10000
class Solution {
public int[][] kClosest(int[][] points, int K) {
}
}
Idea - 1
Sort by distance from origin and take the first K points. Time
and space 
.
class Solution {
public int[][] kClosest(int[][] points, int K) {
int n = points.length;
Arrays.sort( points, new Comparator<int[]>()
{
public int compare(int[] a, int[] b)
{
return dist(a)-dist(b);
}
});
int[][] sol = new int[K][2];
for(int i = 0; i < K; ++i)
{
sol[i] = points[i];
}
return sol;
}
private int dist(int[] p)
{
return p[0]*p[0] + p[1]*p[1];
}
}
Runtime: 26 ms, faster than 69.27% of Java online submissions for K Closest Points to Origin.
Memory Usage: 54.7 MB, less than 92.47% of Java online submissions for K Closest Points to Origin.Idea - 2
Let's take the first K points as a solution candidate. (K+1)-th point can be added to the solution if it improves the situation, therefore, if it is closer to origin than the worst in current solution set. So, keeping a max heap and whenever it has size > K removing the worst would give us the closest K in the end. Time
and space .
class Solution {
public int[][] kClosest(int[][] points, int K) {
int n = points.length;
PriorityQueue<int[]> maxq = new PriorityQueue<int[]>(new Comparator<int[]>()
{
public int compare(int[] a, int[] b)
{
return dist(b)-dist(a);
}
});
for(int[] p : points)
{
maxq.offer(p);
if(maxq.size() > K)
{
maxq.poll();
}
}
int[][] sol = new int[K][2];
int i = 0;
while(!maxq.isEmpty())
{
sol[i++] = maxq.poll();
}
return sol;
}
private int dist(int[] p)
{
return p[0]*p[0] + p[1]*p[1];
}
}
Runtime: 35 ms, faster than 55.95% of Java online submissions for K Closest Points to Origin.
Memory Usage: 63 MB, less than 23.78% of Java online submissions for K Closest Points to Origin.Idea - 3
We can sort the distances and collect K of the ones that are less or equal to K-th in the sorted distance. Time and space .
class Solution {
public int[][] kClosest(int[][] points, int K) {
int n = points.length;
int[] dist = new int[n];
for(int i = 0; i < n; ++i)
{
dist[i] = dist(points[i]);
}
Arrays.sort(dist);
int Kth = dist[K-1];
int[][] sol = new int[K][2];
int j = 0;
for(int i = 0; i < n && j < K; ++i)
{
if(dist(points[i]) <= Kth)
{
sol[j++] = points[i];
}
}
return sol;
}
private int dist(int[] p)
{
return p[0]*p[0] + p[1]*p[1];
}
}
Runtime: 15 ms, faster than 80.58% of Java online submissions for K Closest Points to Origin.
Memory Usage: 67.3 MB, less than 5.04% of Java online submissions for K Closest Points to Origin.Idea - 4
We can use partitioning idea from quick sort and as soon as the partition is the one we want (the pivot is the K-th in sorted order) we are done. Worst case time is
, however average case is 
. Worst case stack space is and average case stack space is 
.
class Solution {
private static final Random rng = new Random(System.currentTimeMillis()%Integer.MAX_VALUE);
public int[][] kClosest(int[][] points, int K) {
int n = points.length;
int[] dist = new int[n];
for(int i = 0; i < n; ++i)
{
dist[i] = dist(points[i]);
}
partition(dist, 0, n-1, K);
int Kth = dist[K-1];
int[][] sol = new int[K][2];
int j = 0;
for(int i = 0; i < n && j < K; ++i)
{
if(dist(points[i]) <= Kth)
{
sol[j++] = points[i];
}
}
return sol;
}
private void partition(int[] A, int lo, int hi, int K)
{
if(lo > hi)
{
return;
}
int pi = lo+rng.nextInt(hi-lo+1);
int pivot = A[pi];
int i = lo-1, j = hi, k = lo;
while(k <= j)
{
if(A[k] < pivot)
{
swap(A, ++i, k++);
}
else if(A[k] > pivot)
{
swap(A, k, j--);
}
else
{
++k;
}
}
// j-th is the K-th element in the array
if(K==j+1)
{
return;
}
else if(K<j+1)
{
partition(A, lo, j-1, K);
}
else
{
partition(A, j+1, hi, K);
}
}
private void swap(int[] A, int i, int j)
{
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
private int dist(int[] p)
{
return p[0]*p[0] + p[1]*p[1];
}
}
Runtime: 8 ms, faster than 92.25% of Java online submissions for K Closest Points to Origin.
Memory Usage: 60.9 MB, less than 47.54% of Java online submissions for K Closest Points to Origin.
and space 
.
. If 
then we have 
. Thus if two triplets has the same any two elements then the triplets are not unique. We need to ensure that two triplets either have different a’s or different b’s. If we ensure the following two conditions, we would collect all unique solutions:
1. We batch all triplets that have a as the first element but have different b’s. All elements in such a batch thus differ in b and would be considered as unique solutions.
2. After step 1, we now move onto a different a (never considering the a in an earlier batch) and repeat step 1.
We would not miss a solution, because for each solution triplet, the first of its three elements (in sorted order) must be in one of the batches – since we consider each distinct element as the first element in some batch. For that batch, we have considered all distinct elements that come after a (in sorted order) as the second element. Given two elements the third element is uniquely determined.
The algorithm has 
time complexity and 
and space 
.
is a palindrome, then it follows that 
and 
is a palindrome. So, if we find out which 2-length substrings are palindrome then finding if a 4-length substring is a palindrome take 
and num2 = 
. If we sorted the two arrays into one, we would have 
. Here, total number of elements is 5 and the middle element aka 
or the 3rd element (5) in the sorted order is the median. On the other hand, if we had num1 = 
and num2 = 
and the median would be the average of the middle element or 
rd element and the previous element. So, the median is 
. Clearly, if we take 
steps in the merge process and keep track of the currently selected element and the previous as well, we would have all information to compute median.
then we at least have the correct divide in terms of number of elements because i is the number of elements left of i-th index of the first array and j is the number of elements left of j-th index of second array, thus the left half of the divide has ![\max(\textrm{num1}[i-1],\ \textrm{nums2}[j-1])\ \le \min(\textrm{nums1}[i],\ \textrm{nums2}[j])](https://s0.wp.com/latex.php?latex=%5Cmax%28%5Ctextrm%7Bnum1%7D%5Bi-1%5D%2C%5C+%5Ctextrm%7Bnums2%7D%5Bj-1%5D%29%5C+%5Cle+%5Cmin%28%5Ctextrm%7Bnums1%7D%5Bi%5D%2C%5C+%5Ctextrm%7Bnums2%7D%5Bj%5D%29&bg=eae9e6&fg=363431&s=0&c=20201002)
, therefore the left half contains smaller elements and the right half contains bigger elements. For example, below all three division are valid in terms of size of the two halves, but only 3rd is the median divide.
.
We can actually iterate on [imin, imax] (intially imin=0 and imax=m) in binary search fashion and check if the divide is the median divide. Choosing nums1 as the shorter array gives us the desired time complexity of 
.
programmingpuzzles 