K Closest Points To Origin - Leetcode Solution

Problem Statement:

We have a list of points in the plane. Find the K closest points to the origin (0, 0).

Input: points = [[1,3],[-2,2]], K = 1 Output: [[-2,2]]

Input: points = [[3,3],[5,-1],[-2,4]], K = 2 Output: [[3,3],[-2,4]]

Approach:

1. Calculate the distance of each point in the given list from the origin using the distance formula (sqrt(x^2+y^2)).
2. Create a max heap and push the first K points into it.
3. For the remaining points, calculate the distance from the origin and compare it with the maximum distance in the heap.
4. If the new point has a smaller distance, remove the maximum distance from the heap and add the new point.
5. At the end, the heap will contain the K closest points to the origin.

Solution:

We can implement a min heap and store the distances in it instead of the points itself. This will optimize the space used.

Time Complexity: O(nlogk) Space Complexity: O(k)

Here is the python code for the solution:

import heapq class Solution: def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

    heap = []
    for point in points:
        distance = -1*(point[0]**2 + point[1]**2) # calculate negative distance to implement max heap as a min heap
        if len(heap) < K:
            heapq.heappush(heap, (distance, point))
        else:
            if heap[0][0] < distance:
                heapq.heappop(heap)
                heapq.heappush(heap, (distance, point))
    
    result = []
    for element in heap:
        result.append(element[1])
    
    return result

This will give us the K closest points to the origin.

1