K Closest Points to Origin

 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 - x2)2 + (y1 - y2)2).

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

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], k = 2

Output: [[3,3],[-2,4]]

Explanation: The answer [[-2,4],[3,3]] would also be accepted.

Example Walkthrough

Let's illustrate the solution approach with a simple example. Imagine we have the following points and we are tasked with finding the k = 2 closest points to the origin (0, 0):

points = [[1, 3], [2, -2], [5, 4], [-3, 3]]

Following the thought process behind the solution:

We calculate the squared distance from the origin for each point which gives us:

For point [1, 3]: 1^2 + 3^2 = 1 + 9 = 10

For point [2, -2]: 2^2 + (-2)^2 = 4 + 4 = 8

For point [5, 4]: 5^2 + 4^2 = 25 + 16 = 41

For point [-3, 3]: (-3)^2 + 3^2 = 9 + 9 = 18

We sort the points based on their squared distances, without computing the square root:

Sorted points based on squared distances: [[2, -2], [1, 3], [-3, 3], [5, 4]]

Sorted squared distances: [8, 10, 18, 41]

We employ a lambda function in Python to serve as a custom sorting key: lambda p: p[0]*p[0] + p[1]*p[1].

We apply this lambda function within the sort() method to our points list to rearrange the list based on the calculated squared distances:

points.sort(key=lambda p: p[0]*p[0] + p[1]*p[1])

After sorting, points looks like this: [[2, -2], [1, 3], [-3, 3], [5, 4]].

We return the first k elements of the sorted array to get the k closest points. Since k = 2, we return the first two points:

closest_points = points[:k]  # closest_points = [[2, -2], [1, 3]]

With this example, we have effectively walked through the solution approach described in the problem content. We sorted the points by their squared distance from the origin, avoided unnecessary square root computation, and returned the k closest points by slicing the sorted array without altering the original array's order.

Approach1 :

class Solution {

    public int[][] kClosest(int[][] points, int k) {

       

          // Sort the array of points based on their Euclidean distance from the origin

        Arrays.sort(points, (point1, point2) -> {

            // Calculate the squared distance for the first point from the origin

            int distance1 = point1[0] * point1[0] + point1[1] * point1[1];

            // Calculate the squared distance for the second point from the origin

            int distance2 = point2[0] * point2[0] + point2[1] * point2[1];

            // Compare the two distances

            return distance1 - distance2;

        });

        // Return the first k elements of the sorted array, which are the k closest to the origin

        return Arrays.copyOfRange(points, 0, k);

    }

}

List :

public class Solution {

    public static List<List<Integer>> kClosest(List<List<Integer>>  input, int k){

       

input.sort((point1, point2) -> {

          // Calculate the squared distance for point1 from the origin

            int distance1 = point1.get(0) * point1.get(0) + point1.get(1) * point1.get(1);

            // Calculate the squared distance for point2 from the origin

            int distance2 = point2.get(0) * point2.get(0) + point2.get(1) * point2.get(1);

            // Compare the two distances

             return Integer.compare(distance1, distance2);

        });

        // Return the first k elements of the sorted array, which are the k closest to the origin

       

return input.subList(0, k);

       

    }

}

using Sort the array using a custom comparator

import java.util.Arrays;

class Solution {

    public int[][] kClosest(int[][] points, int k) {

        // Step 1: Sort the points array using a custom comparator

        Arrays.sort(points, new java.util.Comparator<int[]>() {

            public int compare(int[] p1, int[] p2) {

                // Calculate squared distance from origin for both points

                int dist1 = p1[0] * p1[0] + p1[1] * p1[1];

                int dist2 = p2[0] * p2[0] + p2[1] * p2[1];

                // Compare the distances

                return dist1 - dist2;

            }

        });

        // Step 2: Take first k points from the sorted array

        int[][] result = new int[k][2];

        for (int i = 0; i < k; i++) {

            result[i] = points[i]; // copy first k points

        }

        return result;

    }

}