K Closest Point points to Origin

#1

I have done heap solution ,but I didn’t understand o(N) Solution ,Help!!

#2

Hey @Bhawna
Please share the link to the question or raise the doubt on the same question :slight_smile:

#3

Actually this is in Leetcode And it is given inside Amazon Interview Questions Pdf in this coding blocks course
Link to Question-https://leetcode.com/problems/k-closest-points-to-origin/

#4

I am not able to understand it myself , I am passing this doubt to some other TA :slight_smile:

#5

ok…

#6

Will any other TA respond or not? Already 4 days passed.

#7

@Bhawna

ur doubt is not there in the live doubts thats why u are not getting any response.
u need to reopen ur doubt so that any other TA can take it

#8

ok…

#9

@Bhawna
are u familiar with quicksort algorithm and working of partition function ?

#10

Yes…

#11

what partition function do? do u know its property?

#12

It makes elements smaller than pivot to left side of it and elements larger than Pivot to it’s right side or we can say it finds correct position of pivot in array

#13

yeah correct.
if i say the pivot index is k then what u can intrepret from this?

#14

Regarding question we need to choose kth index as pivot (k-1) times to have k closest points ,I understood this

#15

yeah
when ur pivot will be at index k that means elements at index [0…k-1] are k smallest in our array .
and that is what we want .(note: here comparision among two point is done on the basis of distance from orgin)

now whats the issue?

#16

How time complexity will be O(N) then??It should be o(NLogN) but we can stop calling left and right of pivot as soon as we find our pivot is kth index.

#17

if index of partitioned element is more than k, then we recur for left part. If index is same as k, we have found the reuired pivot and we return. If index is less than k, then we recur for right part. This reduces the expected complexity from O(n log n) to O(n), with a worst case of O(n^2).

for mathematical proof of time complexities .
pls follow this->link

#18

Okay Understood Completely Thanks…

#19

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.