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 (i.e., √(x1² + y1²)).

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 two closest points are (3, 3) and (-2, 4).

Steps

1. Calculate Distances: For each point, calculate its squared Euclidean distance from the origin (we can avoid the sqrt operation for efficiency as it doesn't change the order of distances).
2. Sort (or Use a Priority Queue): Sort the points based on their calculated squared distances. Alternatively, use a min-heap (priority queue) to efficiently maintain the k closest points seen so far.
3. Return k Closest: Return the first k points from the sorted array (or the contents of the priority queue).

Explanation

The solution leverages the fact that comparing squared distances is equivalent to comparing distances. Avoiding the square root calculation significantly improves performance, especially for a large number of points. The choice between sorting and a priority queue depends on the desired time complexity. Sorting is simpler but less efficient for very large inputs.

Code (Java) - Using a Priority Queue (More Efficient)

import java.util.PriorityQueue;

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> (b[0] - a[0])); // Max heap based on squared distance

        for (int[] point : points) {
            int distSq = point[0] * point[0] + point[1] * point[1];
            int[] entry = new int[]{distSq, point[0], point[1]};
            maxHeap.offer(entry);
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }

        int[][] result = new int[k][2];
        int i = 0;
        while (!maxHeap.isEmpty()) {
            int[] entry = maxHeap.poll();
            result[i][0] = entry[1];
            result[i][1] = entry[2];
            i++;
        }
        return result;
    }
}

Code (Java) - Using Sorting (Simpler, Less Efficient)

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        Arrays.sort(points, (a, b) -> {
            int distA = a[0] * a[0] + a[1] * a[1];
            int distB = b[0] * b[0] + b[1] * b[1];
            return distA - distB;
        });
        return Arrays.copyOfRange(points, 0, k);
    }
}

Complexity

Priority Queue Approach:

• Time Complexity: O(N log k), where N is the number of points. Adding each point to the heap takes O(log k) time.
• Space Complexity: O(k) to store the heap.

Sorting Approach:

• Time Complexity: O(N log N), where N is the number of points.
• Space Complexity: O(1) (in-place sorting, depending on the implementation). Arrays.sort() in Java uses a hybrid approach and its space complexity might be considered O(log N) in worst-case scenarios.

The Priority Queue approach is generally more efficient for large N and small k, while sorting is simpler for smaller datasets.