K Closest Points to Origin

Problem Summary

• Given points in (x,y) format, return k closest points to origin (0,0)

What is Being Asked?

• Calculate distance between points and origin
  • $\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2}$

Approach Taken

• Use Min Heap to store all distances
• Then pop k times smallest distances
• Return the points for each distance

Main Concepts Used

• Heap

Time & Space Complexity

• Time: $O(n+klogn)$ → Reason: Heapify is $O(n)$ and popping from heap is $logn$ and we do this $k$ times
• Space: $O(n)$ → Reason: Storing distances for each point

Code

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        # for each point we need to calculate distance to origin
        # store that in array, heapify it
        # get k min points
        distances = []
        originPoint = [0,0]
        for p in points:
            distances.append((self.calculateDistance(p, originPoint), p))
        heapq.heapify(distances)

        result = []
        for _ in range(k):
            result.append(heapq.heappop(distances)[1])
        return result

    def calculateDistance(self, point1, point2):
        return math.sqrt(((point1[0] - point2[0])**2) + ((point1[1] - point2[1])**2))

Optimized Approach

Quick Select can produce a more optimized approach