K CLOSEST POINTS TO ORIGIN | LEETCODE 973 | PYTHON SOLUTION

In this video we are solving a popular Amazon interview question involving heaps: K Closest Points to Origin.
This is a straightforward question but the heap set up is a bit tricky because we need to use a max heap to keep track of the K smallest elements. This is weird because we usually think of max heaps as storing the largest element so using it to keep track of the K smallest is a bit awkward at first but makes sense conceptually once you think about it.

[@LuisRoel-w6q]

I really enjoy your videos! Thank you for making them. I have taken the concepts you've taught me here and come up with a (imo) simpler solution:
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
heap = []
for x, y in points:
dist = -(x ** 2 + y ** 2) # You don't even really have to calc the distance, since relative order is the same, but we make it negative because of min-heap
if len(heap) < k: # If our heap is not of size k yet
heapq.heappush(heap, (dist, (x, y)))
else:
heapq.heappushpop(heap, (dist, (x, y))) # More efficient than doing a push, then a pop
return [point for _, point in heap]
It should be the same runtime + space complexity as your answer (I think...).
Thanks again for all the great videos! I have learned a lot. Nobody has made it "click" like you have.

[@ashleypowell8066]

If you wanted to split hairs and make it even more optimal, I'm thinking you don't need two for loops or a separate list for the euclidean distances. Cutting these would save n operations and space. I think? Super clever using a max heap. I'm learning a lot from this channel.
heap = []
for x, y in points:
dist = x**2 + y**2 # don't actually need the square root
if len(heap) < k:
heapq.heappush(heap, (-dist, x, y))
elif -dist > heap[0][0]:
heapq.heapreplace(heap, (-dist, x, y))
return [[x, y] for _dist, x, y in heap]

[@mohammadkareem1187]

Great job. Wished if you could have covered this problem using quick select algorithm which is O(N) in time and O(1) in space.

[@crackfaang]

Quick select is bullshit because average time is O(N) but worst case is O(N^2). Unless the interviewer wants to fuck you over and demand only quick select, it’s never worth it to code quick select. I would always recommend mentioning the algorithm exists but say that because worst case is O(N^2), we won’t code it.
Only asshole Google interviewers who want to show off how smart they are (over compensating for something…) will not accept the heap solution 😂

[@mohammadkareem1187]

@@crackfaang Oh, good to know. I had a hard time learning the quick sort/ quick select and still not confident if I can code it during the interview. Thanks man

[@dnm9931]

I love how straightforward and direct you are man 😂😂😂

[@dnm9931]

Thanks soo much again! You are appreciated

[@preityhansaa9150]

Hi Thanks for taking time to post the videos! can you also post for
1091Shortest Path in Binary Matrix

636 Exclusive Time of Functions
249 Group Shifted Strings

721 Accounts Merge

[@crackfaang]

Im glad you’re enjoying the content! I have videos for all those problems except “Exclusive Time of Functions” which is on my to-do list. Make sure you subscribe so you don’t miss when that video comes out

[@subee128]

Thanks

[@ValentinoMarin]

cool, most of the time when the problem says K or Kth it means heap/priority queue but not always

[@jyothi9082]

Can you solve problems in java as well? Is there a reason you prefer python?

[@crackfaang]

No unfortunately not. I have zero Java experience and will not be learning it anytime soon. Python is the simplest language out there and is basically runnable pseudocode so it’s easy for anyone to read and understand. Plus it’s my main programming language

[@Ankit-hs9nb]

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

if len(points) < k:
return points

euc_distance_poinst=[]
for x,y in points:

euc_distance = math.sqrt(x**2 +y**2)
euc_distance_poinst.append([euc_distance,x,y])

heapq.heapify(euc_distance_poinst)
result=[]
while k>0:
_,x,y=heapq.heappop(euc_distance_poinst)
result.append((x,y))
k -=1

return result
we could have done using min heap; what's wrong with that?

[@crackfaang]

You shouldn’t just throw all the values into a min heap because
1). You waste space. You are only concerned with the top K values and there’s no reason to put all values into the heap (unless K == len(nums)). You go from O(K) space to O(N).
2). Second issue here is that you need to reshuffle the heap when popping the values when you get your final K from the heap. If you just maintain K items then you don’t need to do removals and remember each removal costs O(K) time where K is the number of elements in the heap

[@Ankit-hs9nb]

@@crackfaang oh ok! Got it! Thanks!