[Programming Problem] K Closest Points to Origin

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.

[problem link]

  • 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;
    }
}

softwareeveryday

9,861 thoughts on “[Programming Problem] K Closest Points to Origin”

  8. I definitely wanted to make a small comment to be able to thank you for these magnificent tips and tricks you are showing on this site. My extended internet search has now been recognized with sensible suggestions to share with my neighbours. I ‘d declare that many of us visitors actually are really lucky to dwell in a perfect place with so many brilliant professionals with great secrets. I feel really lucky to have come across the site and look forward to really more brilliant minutes reading here. Thanks again for a lot of things.

    Reply

  9. Thanks a lot for providing individuals with an extremely special possiblity to read in detail from here. It’s always so pleasing and as well , jam-packed with fun for me personally and my office peers to search your website at minimum thrice every week to read the fresh stuff you have got. And lastly, I’m also usually happy considering the dazzling hints served by you. Certain 4 facts in this article are undoubtedly the very best we have all had.

    Reply

  10. A lot of thanks for your entire hard work on this site. Ellie loves making time for investigation and it’s simple to grasp why. I learn all concerning the powerful medium you produce insightful tricks by means of your website and strongly encourage response from some others on this theme plus our simple princess is always studying a lot. Have fun with the rest of the year. Your conducting a useful job.

    Reply

  11. Needed to draft you that very little word in order to say thanks a lot the moment again on the gorgeous pointers you have contributed above. It was surprisingly open-handed of people like you to offer unreservedly what many individuals would’ve advertised for an e-book to get some money on their own, mostly since you could possibly have done it if you considered necessary. These strategies as well worked to be the fantastic way to recognize that most people have similar desire really like mine to know much more in regard to this condition. I am certain there are lots of more pleasant opportunities in the future for people who looked at your site.

    Reply

  12. I wish to convey my appreciation for your generosity giving support to folks that really need assistance with your area. Your real commitment to getting the message all around turned out to be amazingly useful and have always permitted regular people much like me to realize their targets. Your entire helpful recommendations denotes so much a person like me and somewhat more to my peers. With thanks; from all of us.

    Reply

  13. I needed to put you one little bit of note to finally thank you over again for your fantastic advice you have provided above. This is really surprisingly open-handed of people like you to convey easily exactly what most people would’ve marketed for an ebook to help with making some dough on their own, notably considering that you could possibly have tried it if you ever considered necessary. Those thoughts as well acted to be a good way to know that other people have the same eagerness much like my own to see great deal more with regard to this condition. I believe there are a lot more fun occasions ahead for those who looked over your site.

    Reply

  14. I have to get across my appreciation for your kindness giving support to folks who absolutely need assistance with that study. Your personal commitment to passing the solution across came to be exceedingly helpful and has usually helped individuals like me to realize their pursuits. Your personal warm and friendly instruction implies a lot to me and especially to my peers. Thanks a lot; from everyone of us.

    Reply

  15. I must show my passion for your generosity for persons who really want assistance with this topic. Your personal commitment to passing the message across had become extraordinarily good and have regularly encouraged those just like me to realize their endeavors. Your own warm and friendly instruction signifies a great deal a person like me and even more to my mates. Many thanks; from each one of us.

    Reply

  16. I truly wanted to jot down a small comment in order to thank you for some of the amazing items you are giving here. My incredibly long internet search has finally been paid with reputable points to share with my friends. I ‘d mention that we visitors are very much lucky to exist in a really good community with so many awesome professionals with insightful solutions. I feel extremely grateful to have seen your entire webpage and look forward to some more pleasurable minutes reading here. Thanks a lot once again for everything.

    Reply

  17. I would like to point out my passion for your kind-heartedness in support of individuals that need guidance on this issue. Your special dedication to getting the message all through appears to be incredibly significant and have really made others just like me to attain their pursuits. This helpful facts implies this much a person like me and extremely more to my office workers. Thanks a lot; from each one of us.

    Reply

  18. I intended to write you that very small remark so as to say thank you once again about the lovely basics you’ve shared here. This is really strangely generous with you to deliver without restraint just what a number of people might have made available as an ebook in making some profit for their own end, and in particular given that you could have tried it if you considered necessary. The creative ideas likewise worked to provide a easy way to be certain that other people online have similar eagerness like mine to figure out a little more regarding this issue. I believe there are some more pleasurable times up front for people who start reading your website.

    Reply