CareerCup

Above solutions are too trivial, a better solution would be
compute x^2 + y^2 (no need sqrt!) and transform into another array. O(n)
Next,
build a Max Heap (Q) out of the first k elements in the array. ---> O(k)
For all elements from k+1..n , if a[i] < Q.min() ,
then Q.replace(Q.min() , a[i])
Q.downheap()
The above loop will take a total time of O(nlogk) in the worst case.

After the loop terminates, the contents of the heap is the k closest elements to the origin.
The total running time of this algorithm = O(n + nlogk)

If you use the trivial sorting method, it will take O(nlogn) . If n is very large, and if k is small, then you can see how inefficient sorting is.

compute euclidean distance and sort by distance

d = sqrt(x*x + y*y)
get min(d) by comparing after each computation d = ..

The trick is that you dont have to compute all distances :-) Try to come up with a partitioning algorithm that computes distance only for K Points and not more :-)

I am sorry, you need to compute the distances but not sort them :P You can use a linear implementation of an algorithm that searches K minimum elements in an Array.

abhijeet is right.
use the select algorithm (en.wikipedia.org/wiki/Selection_algorithm)to find the kth minimum element ,this takes o(n) time.after finding the kth minimum element iterate over the array to find all the elements less than the kth minimum element found.so overall complexity is o(n).

guyz there are really smart people browsing this site,no wonder many problems dont have their solutions posted.

and, you are one of those 'smart' people.

bhaiyon jhagda mat karo yaron!!!!
@dingdong wat ur saying man select jus takes o(1) space,u dont need auxillary array to compute the kth smallest element.

dbdgfdgfdgfdgf

1. Create a Max Heap with the first k points using the distance factor..
2. For each remaining point, insert it in the Max Heap and then delete the max value from the heap.
3. The heap now contains the min k points.
4. This algorithm is O(n log m), where m is the number of points we are looking for.

1. calculate the distance of each point from the origin
2. Pick the first point P1, let its distance be R1.
3. Find no. of points which are inside the circle of radius R1, lets call them NR.
Three cases
a. if NR > K R1 = R1/2
b. if NR == K we are done
c. else R1 = R1*2
repeat step 3.

1. Calculate the distances of each point once and store the distances in an array. O(N).
2. Now find the kth smallest distance in the array using Selection Rank algorithm. O(k).
3. Iterate over the N points again from the beginning and get all points whose distance is less than or equal to k and write them onto your k-size array. O(N).
considering N>>>k then total time complexity O(N).

Check this out O(2n) using a quicksort mod. nice..
google: "Find Kth minimum element in a unsorted array ashish yadav" (donno why I can't put the link here!!)

use K-D trees if you have the all the points in the plain at the beginning.
And also this approach can be extended to points in k dimensions.

below link might help, how to create K-D trees:
ms-amazon.blogspot.in/2013/06/implementation-of-k-dtrees.html