Untitled

import java.util.Random;

public class ClosestPointsQuickSelect {
    public static int[][] kClosest(int[][] points, int k) {
        quickSelect(points, 0, points.length - 1, k);
        int[][] result = new int[k][2];
        System.arraycopy(points, 0, result, 0, k); // Copy first k points
        return result;
    }

    private static void quickSelect(int[][] points, int left, int right, int k) {
        if (left >= right) return;

        // Partition the points array and get the pivot index
        int pivotIndex = partition(points, left, right);

        // If partitionIndex equals k, we have the k closest points
        if (pivotIndex == k - 1) return;
        else if (pivotIndex < k - 1) {
            // Recur on the right side
            quickSelect(points, pivotIndex + 1, right, k);
        } else {
            // Recur on the left side
            quickSelect(points, left, pivotIndex - 1, k);
        }
    }

    private static int partition(int[][] points, int left, int right) {
        // Select a random pivot and move it to the end
        int pivotIndex = left + new Random().nextInt(right - left + 1);
        swap(points, pivotIndex, right);

        int[] pivot = points[right];
        int pivotDist = squaredDistance(pivot);
        int i = left;

        for (int j = left; j < right; j++) {
            if (squaredDistance(points[j]) <= pivotDist) {
                // Swap points[i] and points[j]
                swap(points, i, j);
                i++;
            }
        }

        // Place the pivot in its correct position
        swap(points, i, right);
        return i;
    }

    private static int squaredDistance(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }

    private static void swap(int[][] points, int i, int j) {
        int[] temp = points[i];
        points[i] = points[j];
        points[j] = temp;
    }

    public static void main(String[] args) {
        int[][] points = {{1, 3}, {-2, 2}, {5, 8}, {0, 1}};
        int k = 2;

        int[][] closest = kClosest(points, k);
        System.out.println("The " + k + " closest points to the origin are:");
        for (int[] point : closest) {
            System.out.println("[" + point[0] + ", " + point[1] + "]");
        }
    }
}