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) {
        Random random = new Random();

        while (left <= right) {
            // Randomize pivot and partition the array
            int pivotIndex = left + random.nextInt(right - left + 1);
            swap(points, pivotIndex, right); // Move pivot to the end
            int partitionIndex = partition(points, left, right);

            // Check if we have found the k closest points
            if (partitionIndex == k - 1) {
                return; // The first k points are now closest to the origin
            } else if (partitionIndex < k - 1) {
                left = partitionIndex + 1; // Move to the right part
            } else {
                right = partitionIndex - 1; // Move to the left part
            }
        }
    }

    private static int partition(int[][] points, int left, int 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, j);
                i++;
            }
        }

        swap(points, i, right); // Place pivot in its correct position
        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] + "]");
        }
    }
}