973. K Closest Points to Origin — LeetCode(Python)

I got you!

Problem:

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Example 1:

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.

Constraints:

  • 1 <= k <= points.length <= 104
  • -104 < xi, yi < 104

Solution:

1. Dynamic Heap Creation —

Explanation —

We iterate over all points in the list points. While doing so, we calculate the distance a given point is away from the origin.

Then, a tuple containing this distance and the point is pushed into our heap.

Note that while pushing into the heap, the negative of the distance d is considered. This is because we are trying to create a maxheap, since we need to pop out the larger elements so that the points closest to the origin are left inside the heap.

If the number of elements in the heap is greater than k, we pop an element from the heap.

Finally, we return the coordinates that are left in the heap as they are the coordinates with the least amount of distance.

Time and Space Complexity —

However, pushing and popping from the heap are logarithmic time operations. This changes the overall time complexity of our code.

Also, we require a linear amount of extra space to store our heap.

Thus, if n is the length of the array nums,

Time Complexity: O(nlogn)

Space Complexity: O(k)

As we can see, this algorithm is no better than just sorting the coordinates by distance. So, we improve upon this approach in the next part of the solution.

2. Popping After heapify —

Explanation —

We then, heapify this list creating a minheap.

Finally, we pop out the first k elements from the heap, store it in a result array and return the result.

Time and Space Complexity —

And pushing and popping from the heap is a logarithmic time operation.

Also, we require a linear amount of auxiliary space to store the heap.

Thus, if n is the length of the list points,

Time Complexity: O(n + klogn)

Space Complexity: O(n)

Even though we took a hit on our space complexity, our runtime improved significantly.

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store