Find the K closest points to the origin in 2D plane, given an array containing N

Question

Find the K closest points to the origin in 2D plane, given an array containing N points. You can assume K is much smaller than N and N is very large. You need only use standard math operators (addition, subtraction, multi, and division).

You may use collections/containers found in the JDK or the standard template library. Your solution will be evaluated on correctness, runtime complexity (big-O), and adherence to coding best practices. A complete answer will include the following:

Find the K closest points to the origin in 2D plane, given an array containing N points. You can assume K is much smaller than N and N is very large. You need only use standard math operators (addition, subtraction, multi, and division). You may use collections/containers found in the JDK or the standard template library. Your solution will be evaluated on correctness, runtime complexity (big-O), and adherence to coding best practices. A complete answer will include the following: Document your assumptions Explain your approach and how you intend to solve the problem Provide code comments where applicable Explain the big-O run time complexity of your solution. Justify your answer. Identify any additional data structures you used and justify why you used them. Only provide your best answer to the question.

Explanation / Answer

The solution that I have figured out is to save the 2d points in an array. For the first k points, find the distance of each point from the origin and build a max heap. For the remaining points , calculate distance from the origin , say dist. If dist is greater than the topmost element of the heap, then change topmost element of heap to dist and run the heapify() procedure.

This would take O(k) to build the heap and O((n-k)log k) for heapify() procedure , thus the total complexity = O(n log k)




What you're looking for is partial sorting.

I think the best way is to put everything into an unsorted array and then do use a modified in-place quicksort which ignores partitions whose indices are entirely above or entirely below k, and use distance from origin as your comparison.

Pseudocode from the wikipedia article above:

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.