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 [[-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: Calculate the squared Euclidean distance of each point from the origin. We use squared distance to avoid the computationally expensive square root operation. The order remains the same since squaring is a monotonically increasing function for positive numbers.

2. Sort: Sort the points based on their squared distances in ascending order. We can use a sorting algorithm like sort with a custom comparator.

3. Return Top k: Return the first k points from the sorted array.

Explanation

The solution leverages the fact that comparing squared distances is equivalent to comparing distances. This optimization significantly improves performance, especially for a large number of points. Sorting efficiently finds the k closest points.

Code

function kClosest(points: number[][], k: number): number[][] {
    // Calculate squared distances
    points.forEach(point => {
        point.push(point[0] * point[0] + point[1] * point[1]); //add squared distance to each point
    });

    // Sort points based on squared distance (last element)
    points.sort((a, b) => a[2] - b[2]);

    // Return the first k points (excluding squared distance)
    return points.slice(0, k).map(point => point.slice(0, 2));
};

Complexity

• Time Complexity: O(N log N), where N is the number of points. This is dominated by the sorting step.
• Space Complexity: O(log N) in the best and average cases for sorting (depending on the specific sorting algorithm used), or O(N) in the worst case if the sorting algorithm requires additional space. In this case, the space used by sort depends on the implementation but is typically close to O(log N). The space used by the map operation is O(k), which is negligible compared to the size of the input array.