K Closest Points to Origin medium

Problem Statement

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: √((x1 - x2)² + (y1 - y2)²).

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 output is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], k = 2 Output: [[3,3],[-2,4]] Explanation: The distance between (3, 3) and the origin is sqrt(18). The distance between (5, -1) and the origin is sqrt(26). The distance between (-2, 4) and the origin is sqrt(20). The distances are sqrt(18), sqrt(26), sqrt(20) respectively. The two closest points are [3,3], [-2,4].

Steps:

1. Calculate Distances: Compute the squared Euclidean distance of each point from the origin. We use squared distance to avoid the computationally expensive square root operation. The relative order of distances remains the same.

2. Sort: Sort the points based on their squared distances. We can use a built-in sorting function with a custom comparer or a priority queue (min-heap).

3. Return k Closest: Select the first k points from the sorted array.

Explanation:

The core idea is to leverage efficient sorting algorithms to find the k closest points quickly. Using squared distances avoids the overhead of repeatedly calculating square roots. The choice between a custom sort and a priority queue depends on the specific constraints and preferences. For smaller datasets, a custom sort might be simpler; for larger datasets, a priority queue (like a min-heap) offers better asymptotic performance for finding the top k elements.

Code:

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int[][] KClosest(int[][] points, int k) {
        // Calculate squared distances and store with points
        List<(int[], int)> pointsWithDistances = new List<(int[], int)>();
        foreach (int[] point in points) {
            int distSq = point[0] * point[0] + point[1] * point[1];
            pointsWithDistances.Add((point, distSq));
        }

        // Sort by squared distance
        pointsWithDistances.Sort((a, b) => a.Item2.CompareTo(b.Item2));

        // Return the k closest points
        int[][] result = new int[k][];
        for (int i = 0; i < k; i++) {
            result[i] = pointsWithDistances[i].Item1;
        }
        return result;
    }
}

Complexity:

• Time Complexity: O(N log N), where N is the number of points. This is dominated by the sorting step.
• Space Complexity: O(N) in the worst case to store the points and distances. If we modify the input array in-place, we could reduce space complexity to O(1) (but this is generally less readable and can be less efficient). The space used by the result array is O(k).