K Closest points

973.K Closest Points to Origin

Array

Heap

Divide and Conquer

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).

Solution 1: Max Heap Approach

Uses a max heap of size k to maintain the k closest points. Each new point replaces the maximum if it's closer to origin.

Time Complexity: O(NlogK) - Each insertion takes logK time
Space Complexity: O(K) - For storing K elements in heap

public int[][] kClosestHEAP(int[][] points, int k) {
    // Max heap ordered by distance from origin
    PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> dist(b) - dist(a));
    
    // Add points to heap, maintaining size k
    for (int[] point : points) {
        q.offer(point);
        if (q.size() > k) q.poll();  // Remove farthest point if over size k
    }

    // Create result array from heap
    int[][] res = new int[k][2];
    for (int i = 0; i < k; i++) 
        res[i] = q.poll();
    
    return res;
}
 
// Calculate squared distance from origin
int dist(int[] point) {
    return point[0] * point[0] + point[1] * point[1];
}

Solution 2: QuickSelect Approach

Uses the QuickSelect algorithm (variant of QuickSort) to find the k closest points. Only needs to partition until the kth element is in correct position.

Time Complexity: O(N) average case, O(N²) worst case
Space Complexity: O(1) - In-place partitioning

public int[][] kClosest(int[][] points, int k) {
    quickSelect(points, k, 0, points.length - 1);
    return Arrays.copyOf(points, k);
}

private void quickSelect(int[][] points, int k, int low, int high) {
    int pivotIndex = partition(points, low, high);

    if (pivotIndex == k - 1) // Found kth position
        return;
    else if (pivotIndex > k - 1)  // Search left half
        quickSelect(points, k, low, pivotIndex - 1);
    else  // Search right half
        quickSelect(points, k, pivotIndex + 1, high);
}

private int partition(int[][] points, int low, int high) {
    int[] pivot = points[high];
    int pivotDist = squaredDistance(pivot);
    int pIndex = low;

    for (int i = low; i < high; i++) {
        if (squaredDistance(points[i]) < pivotDist) {
            swap(points, i, pIndex++);
        }
    }

    swap(points, pIndex, high);
    return pIndex;
}

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

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