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

I got you!

# Problem:

Given an array of `points`

where `points[i] = [xi, yi]`

represents a point on the **X-Y** plane and an integer `k`

, return the `k`

closest points to the origin `(0, 0)`

.

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 can use a heap data structure to solve this problem.

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 —

The creation of a heap is a linear time operation.

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 —

In this case, we first store all the coordinates along with their distance from the origin in a new list.

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 —

Creating the list and heapifying it is a linear time operation.

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.