FIFA-2022 Career Guide Free Tutorials Go to Your University Placement Preparation 
0 like 0 dislike
761 views
in Coding Questions by Goeduhub's Expert (2.3k points)

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. 1 <= K <= points.length <= 10000
  2. -10000 < points[i][0] < 10000
  3. -10000 < points[i][1] < 10000

1 Answer

0 like 0 dislike
by Goeduhub's Expert (2.3k points)
 
Best answer

We keep a min heap of size K.

For each item, we insert an item to our heap.

If inserting an item makes heap size larger than k, then we immediately pop an item after inserting ( heappushpop ).

Runtime:

Inserting an item to a heap of size k take O(logK) time.

And we do this for each item points.

So runtime is O(N * logK) where N is the length of points.

Space: O(K) for our heap.

import heapq

class Solution:

    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

        

        heap = []

        

        for (x, y) in points:

            dist = -(x*x + y*y)

            if len(heap) == K:

                heapq.heappushpop(heap, (dist, x, y))

            else:

                heapq.heappush(heap, (dist, x, y))

        

        return [(x,y) for (dist,x, y) in heap]

eg : points = [[1,3],[-2,2]] 

K = 1

ans = Solution()

ans.kClosest(points, K)

Output-

[[-2,2]]

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.

Best Data Science Courses on Datacamp
Best Data Science Courses on Coursera
Best Data Science Courses on Udemy
Best Data Science Courses on Pluralsight
Best Data Science Courses & Microdegrees on Udacity
Best Artificial Intelligence[AI] Courses on Coursera
Best Machine Learning[ML] Courses on Coursera
Best Python Programming Courses on Coursera
Best Artificial Intelligence[AI] Courses on Udemy
Best Python Programming Courses on Udemy

Related questions

0 like 0 dislike
1 answer 1.2k views
asked Sep 11, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 271 views
asked Sep 11, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 1.5k views
0 like 0 dislike
1 answer 762 views
asked Sep 5, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 466 views
asked Sep 11, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)

 Important Lists:

Important Lists, Exams & Cutoffs Exams after Graduation PSUs

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy ||  Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 

 

Free Online Directory

...