Solution Explanation for LeetCode 973: K Closest Points to Origin

This problem asks to find the k points in a given array that are closest to the origin (0, 0). Several approaches can solve this efficiently. We'll analyze three: sorting, using a max-heap, and binary search.

Solution 1: Sorting

This is the most straightforward approach. We calculate the Euclidean distance of each point from the origin using the formula √(x² + y²). Then, we sort the points based on their distances. Finally, we return the first k points from the sorted array.

Code (Python):

import math
 
class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        points.sort(key=lambda p: math.hypot(p[0], p[1])) #Sort based on distance
        return points[:k] #Return first k elements

Time Complexity: O(n log n), dominated by the sorting step. n is the number of points. Space Complexity: O(log n) in most cases due to sorting (in-place merge sort has logarithmic space complexity). Could be O(n) in the worst case for some sorting implementations.

Solution 2: Max Heap (Priority Queue)

A more efficient approach, especially when k is significantly smaller than n, uses a max-heap. We maintain a max-heap of size k. As we iterate through the points, we add each point to the heap. If the heap size exceeds k, we remove the point with the largest distance (the farthest point). At the end, the heap contains the k closest points.

Code (Python):

import heapq
 
class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        heap = []
        for x, y in points:
            dist = -(x**2 + y**2) #Negate to make it a max heap
            heapq.heappush(heap, (dist, [x, y])) #Push distance and point
            if len(heap) > k:
                heapq.heappop(heap) #Remove the farthest if more than k points are present
        return [point for dist, point in heap] #Return the points in the heap

Time Complexity: O(n log k). We iterate through n points, and each heap operation takes O(log k) time. Space Complexity: O(k) to store the heap.

Solution 3: Binary Search

This approach is based on the observation that the distances are sorted implicitly. We can find a critical distance such that all points within this distance include exactly k closest points. We use binary search to efficiently find this critical distance.

Code (Python):

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        distances = [(x*x + y*y, i) for i, (x, y) in enumerate(points)]
        left, right = 0, max(dist for dist, i in distances) #Find the maximum distance
        while left < right:
            mid = (left + right) // 2
            count = sum(1 for dist, i in distances if dist <= mid)
            if count >= k:
                right = mid
            else:
                left = mid + 1
        return [points[i] for dist, i in distances if dist <= right]

Time Complexity: O(n log M), where M is the maximum distance. The binary search takes O(log M) time, and in each iteration, we count the number of points which take O(n) time. Space Complexity: O(n) to store distances. This approach might not be ideal if the distance range (M) is very large.

Summary:

| Approach | Time Complexity | Space Complexity | Notes | |----------------|-----------------|-----------------|-------------------------------------------------| | Sorting | O(n log n) | O(log n) or O(n) | Simple, but less efficient for large n and small k | | Max Heap | O(n log k) | O(k) | Efficient for large n and small k | | Binary Search | O(n log M) | O(n) | Depends on the range of distances (M) |

The best approach depends on the specific constraints of the input. If k is much smaller than n, the max-heap approach is usually the most efficient. If k is close to n, sorting might be simpler and faster in practice due to the constant factors involved in the heap. Binary search is generally less practical for this problem unless the distances are exceptionally distributed.