K Closest Points to Origin - Leetcode 973 - Heaps (Python)

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@user-jm6gp2qc8x]

its so wonderful to realise that this heap DS is helping us to solve a problem that involves k smallest, k largest etc, by not doing a useless sorting all of the elements involved.

[@TheMadisonBluesBand]

Very nicely explained how (n log n), while seemingly similar to (n log k) for trivial inputs, is actually much less efficient.

[@itachicodes2506]

absolute goat at explaining man (:

[@ganeshegmful]

Great. One observation, if two are more points are within the square shaped region (1,1) (-1,-1), then I guess we need to compare the square root of squared sum.

[@galdali10]

That is a really nice and easy to understand solution! But you can also use quick select to improve to O(n)

[@kauegatto]

finally understood this problem, ty a lot!

[@GregHogg]

Glad to hear it, no worries!

[@kumaranb8702]

Nice information 😊

[@tm-luk317]

What is the name of the software he uses as a blackboard?

[@GregHogg]

He uses miro

[@deeps-n5y]

@@GregHogg 😂

[@tashrique]

# Quick Select Aprroach # O(n), O(1) distance = lambda point: point[0]**2 + point[1]**2 def quickselect(l, r): index = random.randint(l,r) pivot = points[index] pivot_dist = distance(pivot) points[index], points[r] = points[r], points[index] p = l for i in range(l, r): if pivot_dist >= distance(points[i]): points[i], points[p] = points[p], points[i] p += 1 points[p], points[r] = points[r], points[p] return p L, R = 0, len(points) - 1 pivot = len(points) while pivot != k: pivot = quickselect(L, R) if pivot > k: R = pivot - 1 else: L = pivot + 1 return points[:k]

[@miramar-103]

return heapq.nsmallest(k, points, lambda p : math.sqrt(p[0]**2 + p[1]**2))