- Notifications
You must be signed in to change notification settings - Fork2.4k
Description
Bug Report forhttps://neetcode.io/problems/k-closest-points-to-origin
Please describe the bug below and include any steps to reproduce the bug or screenshots if possible.
The time complexity of the Min-Heap solution seems to be wrongly mentioned as O(klogn).
The correct time complexity is O(n + klogn). The reason is that the solution includes two different steps, first the min-heap building step which contains n append operations to the min-heap, which will be n * O(1) = O(n) and then a heapify, which will also be O(n). So, getting the min-heap ready initially, has a time complexity of O(n). The second step of the solution entails k times popping from the heap, which will be O(klogn). The O(n) part is significant and cannot be omitted. The total time complexity comes out to O(n + klogn)