K Closest Points to Origin - Heap / Priority Queue - Leetcode 973 - Python

0:00 - Read the problem
4:23 - Drawing Explanation
7:00 - Coding Explanation

leetcode 973

#sorted #heap #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[sushilkhadka]

I did not know we can heapify the a list list. Thanks man!

[shahidshahmeer]

Hey, I love your videos but this is not the most optimal, or even the 2nd most optimal solution.

You can improve this solution by having a min heap of size k. Then, go through the list of points and add to the heap. If the size of the heap exceeds k, pop from the heap. By the end, your heap will contain the k closest points. This is O(nlogk) time (which is similar to your solution) but only O(k) space, whereas your solution is O(n) space.

There is also an O(n) solution based on quick sort called quick select.

[kwakukusi]

i got this in an amazon interview . I just sorted the array by distance and selected the first K elements. (not the best solution but it passed all the test cases)

[grasstoucher]

I just realize you sound like daily dose of internet

[nicolasguillenc]

I really like this problem, your explanation helped me really understand it. As a js developer I would like to know how to implement a heap during the interview, otherwise I will have to use a sorted array

[mingjuhe]

It's me again. Thank you NeetCode.

[CodingForRealLife]

The first part is O(N logN), looping through the points array then add it to heap, a better solution would be using max heap, this will improve the solution to O(N logK)

[littlebox]

just wondering will be allowed that we use this kind of build-in function like heapify in the interview? BTW I have been watching your videos for a while, it is really really really helpful!

[xmnemonic]

such a bizarre problem. they might as well just give you an array of ints and ask you to heap sort it

[rachelwilliams]

When solving this problem in Ruby, sorting the distances without a min heap was faster.

[alxzheng]

how does heapify know what its key is?

[zeptra]

i dont know how you come up with this kind of solutions, wow

[mikedelta]

Such a clear and efficient explanation

[Vedsten]

Can you explain how heapify is O(n)? To build a binary heap, don't you need to call heap reorder n times making it O(nlog(n))?

[oxyht]

Why do heappop? Direct use indexing. O(n + k) solution

[GingeBreadBoy]

Quick Select with Random Selects, O(N) average time. I chose quick select here because all data was present (no stream) and we are not performing any transformative operations on the actual inputs (as in last stone weight).

"""
We have points Xi, Yi, and an integer k.
We want the K-closest points to the origin.

We could use a heap to solve this problem in O(NLogN) (heapify plus popping...)

However a better solution will be to use quick select which gets an average case runtime of O(N) time!
The closests points will have smallest euclidean distances ...

"""

class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
def partition(l, r):

#choose a random pivot
pivot = random.randint(l, r)
pivot_distance =

#move pivot to end
points[pivot], points[r] = points[r], points[pivot]

#store idx for swapping
store_idx = l

for i in range(l, r):
if euclidean_distance(points[i]) < pivot_distance:
points[i], points[store_idx] = points[store_idx], points[i]
store_idx += 1

#switch store_idx with pivot
points[r], points[store_idx] = points[store_idx], points[r]
return store_idx


def quick_select(points, k):

left, right = 0, len(points)-1
pivot_idx = len(points)

#continue parititoning while pivot != k
while pivot_idx != k:
pivot_idx = partition(left, right)

#k smallest lie to the left
if pivot_idx > k:
right = pivot_idx - 1

#the k smallseet lie to the right & to the left of pivot_idx all values smaller, so left = pivot_idx
else:
left = pivot_idx

#return k closest points
return points[:k]

def euclidean_distance(point):
x, y = point
return math.sqrt(x**2+y**2)

#perform quick select and return k smallest
return quick_select(points, k)

[sahithrao]

Can you explain bounded robot in the next video?

[xpstarter]

Correction: Heapify is O(logn), here its refering to build heap which is O(n)

[z.l.]

this could actually be solved using quick select in O(n) and O(1), not sure if heap solution is acceptable in an f and g equivalent interview

[dheerajgadwala]

Time Complexity: O(n + klog(n)) right?