Amazon Coding Interview Question - K Closest Points to the Origin

Key Takeaways

here's a coding interview problem from Amazon we have an array of two posts or an array of arrays of two items each this represents points on a two-dimensional space so for example this first item - 2 4 represents this point right here because the x-coordinate of this point is minus 2 and the y coordinate of this point is 4 and the problem is this given these points how would you find that K closest points to the origin and of course the origin is at 0 0 so for example if the given K is 2 how would you find the two closest points to the origin out of these points the two closest points here are minus 1 0 and 0 minus 2 so you should be able to print these points and try solving this problem in a more general way to practice pause the video right here and think about how you would solve the problem and then come back to the video the first natural step for solving this problem is to find the distance to each point from the origin and of course we can use the Pythagorean theorem to do that so to find the distance to for example at this point minus 2 4 we can just find the value of square root of minus 2 squared plus 4 squared which is equal to square root of 4 plus 16 which is square root of 20 so that's the distance from the origin to minus 2 4 and we can go through the same procedure for every other point to find the distance for every other point as well and after that you can just construct a new array with objects containing the coordinates of each point as well as the distance to each point from the origin and this new array might look like this I'm calling this new array points with D as in points with distance and the first object of this new array will correspond to the first item in the original array with the coordinate - - for and with this s square root of 20 of course and we're going to have the same type of object for every other point in the original points so the length of points with T the new array will be the same as the length of the original array points and you can use dictionaries or hash tables to store this information instead of using objects as well once you have this array all you need to do is you just need to find the K objects or the K points with the shortest distance so at this point this problem is actually equivalent to the problem of finding the K smallest elements in a given array of numbers for example if the given array is this array of integers and if the given K is 3 we want to be able to find the three smallest items out of this array which are 1 2 and there are right here now there are a few different approaches for solving this problem the simplest approach is the one in which you sort this array in an ascending order so that the smallest items come first and out of the sorted array take the K first items and that approach would take Big O of n log N in time if you use for example quick sort or merge sort another approach is using a variation of something called selection sort and I'm not going to go into detail here in this video but this approach would take big off and K in time now my personal favorite approach is the one in which we use a max-heap and this one would take big of k plus n minus k times log k in time let me explain how it works first of all let's quickly go over what a heap is in a sentence it is an efficient way to keep track of the largest value in the given collection of numbers suppose as an example you're given these three numbers 4 1 & 5 if you construct a max-heap with these three numbers you can sort of visualize it as a bag or a box of the three numbers and however many numbers you have in the max-heap retrieving the largest number out of it is very efficient in fact asking the heap what the largest number is without modifying the heap so just examining what the number is without retrieving the number itself will be done in Big O of one in time now there are a few other operations we're going to use on a heap for this particular problem the first one is create creating a heap a max-heap with K items takes Big O of K in time the second operation is replace so for example if we want to replace the current largest number in the given heap this one with a new number three then this heap will be rearranged so that the current largest number will be four and they will have one and three below it this operation takes Big O of log of K where K is the number of items in heap and the third operation is print off this print all the items in the given heap in the order that's not necessarily sorted so for example this operation on this particular heap might print four one and three and this operation takes Big O of K in time now how can we use a max-heap and those operations on it to find the K smallest items in a given array of numbers let's consider this array of numbers a game and let's say we want to find the three smallest items then the first step will be to construct a max-heap with the first K items or with the first three items after that for each item in the remainder of the array ask ourselves is this number smaller than the current largest number in the heap if it is smaller then replace it with a lakh current largest number so when we are examining this number right here to the heap will look like this and the current largest number has become four and when we're examining this number three four will be replaced wait three we're going to keep going like that and when we're examining this number ten because this is not smaller than the current largest number in the max-heap we'll just ignore that number and at the end of this process just print all items from this heap and we're done we have the K smallest items from the given array now let's quickly recap our entire strategy using pseudocode we're going to define our function closests which takes the given points and K for finding the K closest points to the origin and from this function we're not going to return anything but we're going to print the K closest point and in this function first of all using points create points with D for points with distance an array of objects containing the coordinates as well as the distance to each point from the origin after that using points with D the array of objects create a max-heap with the first K items and use the distance as the key when we create a max-heap let's just call this max heap MH after that run a for loop for each point in the remainder of the array and if this points distance is less than the current max of MH then replace mah is current max with P and once we're done with this for loop then just print all points in image and we're done now what about time complexity let's think about it line by line the first line here using points creating points with D takes Big O of n because we go through this array only once and creating a max-heap with K items as we discussed earlier takes Big O of K in time and here we're running n minus K loops in each loop replacing M H is current point with P takes Big O of log of K and so the runtime for this entire four loop will be big-oh of n minus K times log K in the worst case scenario after that printing all points in image will take Big O of K in time so adding them all up Big O of n plus big of K plus Big O of n minus K times log of K Plus speak of K we're going to have Big O of n plus n minus K times log K and that would be the runtime for this entire solution ok thanks a lot for watching this video if you liked this video I would also recommend my course on udemy you have an essential coding interview questions in which I cover eleven of the most essential coding interview questions to master with coding exercises in Python and Java in case you're interested in taking the course I put a discount code below in the description all right I'll see you in the next video