K Closest Points to Origin
This is just 'Kth largest element' in disguise. The value you are comparing is no longer the element's direct value, but a statistic: namely Pythogorean. But the solutions apply just the same, either maintain max heap of size K and insert each coordinate into it but define your own comparator to be the Pythogorean statistic, and when heap size > K, decide if to discard top element and replace with the new one. Runtime: N*log(K). Or, if you want to risk appearing to memorize solution, do the pivoting algorithm, where you choose a random point and shuffle the elements left and right of it, runtime O(N). The heap solution is much more intuitive to me, but some depraved interviewers may not be satisfied until you come up with the pivoting one. Does that about sum it up?
Nice job summarizing the top voted answer in leetcode discuss.
Just sort the input array with a custom comparator and return the first K elements. No need to mess around with heaps. def returnKClosest(points, k): points.sort(custom_sort) return points[:k] def custom_sort(a, b): aDistance = a[0]**2 + a[1]**2 bDistance = b[0]**2 + b[1]**2 if aDistance <= bDistance: return -1 else: return 1
That’s a big fail my friend! Either you haven’t read the OP or, worse, you didn’t get it. Which is why you’re counter-proposing an O(N LogN) algo instead of Quick Select with the same custom comparator which is O(N).
Your code still works if you remove the **2 right I thought Python3 doesn't have comparators built in anymore right? Need to do something like import functools.cmp_to_key points.sort(cmp_to_key(custom_sort))
Look up selection sort (quick sort), basically you pivot and throw away half the array everytime coz you're looking for values in other half of array. O(N)
Great comments in general. Although I feel bit weird about everyone recognising the pivot algorithm as optimal - sure it’s complexity is O(n) but that’s just for the average case aka you are able to reduce the array size by a fraction. The worst case complexity is O(n^2) (when you are unlucky every time and choose the largest/smallest element in each partitioning). Although in an interview it would make sense for the interviewer to see your comfort level in implementing both the ways (heap and pivot partitioning) - I guess this is one of the questions which are fairly straightforward to understand (after some [leet]coding) but is bit tricky to code - kind of similar to your day to day code.
Quick select is pretty intuitive and easy to implement. The only difference here is a new comparator.
It's not quite linear. It's only linear on average iff k=n/2 roughly, otherwise you will on average need more than one pivot. The number of pivots you need is roughly the number of times k is divisible by 2, or lgk. The first time you run the pivot you need to compare about N elements, the second time N/2 etc. Works out to the same time complexity. The difference is that you are trading off deterministic behavior with a near ideal memory access pattern in the heap for an algo that has little memory footprint but no time guarantees. Which one is best depends on the limits of the problem.
👍