K CLOSEST POINTS TO ORIGIN | LEETCODE 973 | PYTHON SOLUTION

[@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.

[@rishabhdas5576]

This would be O(K) constant space complexity. Far better than O(N) linear space

[@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 😂😂😂

[@TheMadisonBluesBand]

@@dnm9931 Yeah, was not expecting that haha

[@ValentinoMarin]

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

[@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

[@dnm9931]

Thanks soo much again! You are appreciated

[@tajikit]

Why don’t you solve this problem with O(k) space complexity?

[@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

[@subee128]

Thanks

[@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!

[@rishabhdas5576]

I have a better solution that uses O(K) space: def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]: heap = [] for point in points: dist = ((0 - point[0])**2 + (0 - point[1])**2)**0.5 if k > len(heap): heappush(heap, (-1 * dist, point)) else: d, p = heap[0] if d < -1 * dist: heappop(heap) heappush(heap, (-1 * dist, point)) return [point for _, point in heap]