{"id":11348,"date":"2021-11-25T20:08:18","date_gmt":"2021-11-25T20:08:18","guid":{"rendered":"https:\/\/www.softwareeverydayblog.com\/?p=11348"},"modified":"2021-11-25T20:10:28","modified_gmt":"2021-11-25T20:10:28","slug":"programming-problem-k-closest-points-to-origin","status":"publish","type":"post","link":"https:\/\/www.softwareeverydayblog.com\/?p=11348","title":{"rendered":"[Programming Problem] K Closest Points to Origin"},"content":{"rendered":"<p>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).<\/p>\n<p>The distance between two points on the X-Y plane is the Euclidean distance (i.e., \u221a(x1 &#8211; x2)^2 + (y1 &#8211; y2)^2).<\/p>\n<p>You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).<\/p>\n<pre lang=\"text\">\r\nExample 1:\r\nInput: points = [[1,3],[-2,2]], k = 1\r\nOutput: [[-2,2]]\r\nExplanation:\r\nThe distance between (1, 3) and the origin is sqrt(10).\r\nThe distance between (-2, 2) and the origin is sqrt(8).\r\nSince sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.\r\nWe only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].\r\n\r\nExample 2:\r\nInput: points = [[3,3],[5,-1],[-2,4]], k = 2\r\nOutput: [[3,3],[-2,4]]\r\nExplanation: The answer [[-2,4],[3,3]] would also be accepted.\r\n<\/pre>\n<p>[<a href=\"https:\/\/leetcode.com\/problems\/k-closest-points-to-origin\/\" rel=\"noopener\" target=\"_blank\">problem link<\/a>]<\/p>\n<ul>\n<li>Create point object that contains x, y co-ordinates and distance from origin.<\/li>\n<li>Keep adding points to max heap. Custom comparator that uses distance (inside the point object) as key.<\/li>\n<li>Make sure size of heap does not go higher than K<\/li>\n<li>In the end, the K points in the heap are your solution<\/li>\n<li>Since size of heap capped at k, Time complexity nlogK Time complexity logK<\/li>\n<\/ul>\n<pre lang=\"java\">\r\nimport java.util.*;\r\n\r\nclass Point {\r\n    int x;\r\n    int y;\r\n    double dist;\r\n    public Point(int x, int y) {\r\n        this.x = x;\r\n        this.y = y;\r\n        this.dist = Math.sqrt(Math.pow(x * 1.0, 2) + Math.pow(y * 1.0, 2));\r\n    }\r\n}\r\n\r\nclass Solution {\r\n    public int[][] kClosest(int[][] points, int k) {\r\n        PriorityQueue maxHeap = new PriorityQueue<Point>((x, y) -> Double.compare(y.dist, x.dist));\r\n        for (int i = 0 ; i < points.length ; i++ ) {\r\n            maxHeap.offer(new Point(points[i][0], points[i][1]));\r\n            if (maxHeap.size() >= k+1) maxHeap.poll();\r\n        }\r\n        \r\n        int ret[][] = new int[maxHeap.size()][2];\r\n        int i = 0;\r\n        while (maxHeap.size() > 0) {\r\n            Point p = (Point) maxHeap.poll();\r\n            ret[i][0] = p.x;\r\n            ret[i][1] = p.y;\r\n            i++;\r\n        }\r\n        \r\n        return ret;\r\n    }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>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., \u221a(x1 &#8211; x2)^2 + (y1 &#8211; y2)^2). You may return [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-11348","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11348","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=11348"}],"version-history":[{"count":3,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11348\/revisions"}],"predecessor-version":[{"id":11351,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11348\/revisions\/11351"}],"wp:attachment":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=11348"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=11348"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=11348"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}