K Closest Points to Origin

class Solution {
public:
    vector<vector<int>> findKClosest(vector<vector<int>>& points, int k) {
        return performQuickSelect(points, k);
    }
    
private:
    vector<vector<int>> performQuickSelect(vector<vector<int>>& points, int k) {
        int start = 0, end = points.size() - 1;
        int pivotIdx = points.size();
        while (pivotIdx != k) {
            pivotIdx = divide(points, start, end);
            if (pivotIdx < k) {
                start = pivotIdx;
            } else {
                end = pivotIdx - 1;
            }
        }
        
        return vector<vector<int>>(points.begin(), points.begin() + k);
    };

    int divide(vector<vector<int>>& points, int start, int end) {
        vector<int>& pivotElement = pickPivot(points, start, end);
        int pivotDistance = calculateDistance(pivotElement);
        while (start < end) {
            if (calculateDistance(points[start]) >= pivotDistance) {
                points[start].swap(points[end]);
                end--;
            } else {
                start++;
            }
        }
        
        if (calculateDistance(points[start]) < pivotDistance)
            start++;
        return start;
    };

    vector<int>& pickPivot(vector<vector<int>>& points, int start, int end) {
        return points[start + (end - start) / 2];
    }
    
    int calculateDistance(vector<int>& point) {
        return point[0] * point[0] + point[1] * point[1];
    }
};

The provided C++ code defines a solution for finding the k closest points to the origin from a list of points in a 2D plane using a modified quickselect algorithm.

The Solution class contains three primary functions apart from findKClosest:

1. performQuickSelect: This function manages the quick select process. It initializes start and end pointers at the beginning and the end of the points array. It uses these pointers to refine the search space in each iteration based on the results from the divide function. This continues until the pivot index is equal to k, ensuring that the first k elements of the array are the ones closest to the origin.

2. divide: This function operates similarly to the partition function in quicksort. It selects a pivot using pickPivot, calculates its distance from the origin, and rearranges elements in points so that elements less than the pivot come before it and all elements greater come after it. The function returns the final position of the pivot, helping performQuickSelect adjust its search range.

3. pickPivot: It selects a middle element as the pivot to be used in divide. This choice can mitigate the effects of a poorly chosen pivot, such as might happen with sorted or nearly sorted input data.

4. calculateDistance: A helper method that computes the squared Euclidean distance from the origin for a given point, which avoids the computational cost of square roots and is sufficient for comparison purposes.

The working process involves:

• Choosing a pivot and dividing the points into segments more and less distant than the pivot.
• Iteratively adjusting the pivot position until the k smallest elements are isolated.
• Returning the result as the required list of k closest points.

The algorithm emphasizes efficiency by focusing only on identifying the k smallest elements rather than fully sorting the data, which is typically more resource-intensive. This method is particularly suitable for large datasets where finding the exact order of all elements is unnecessary.

class Solution {
    public int[][] kNearest(int[][] points, int k) {
        return selectKClosest(points, k);
    }
    
    private int[][] selectKClosest(int[][] points, int k) {
        int lower = 0, upper = points.length - 1;
        int pivotIdx = points.length;
        while (pivotIdx != k) {
            pivotIdx = partitionPoints(points, lower, upper);
            if (pivotIdx < k) {
                lower = pivotIdx;
            } else {
                upper = pivotIdx - 1;
            }
        }
        
        return Arrays.copyOf(points, k);
    }

    private int partitionPoints(int[][] points, int lower, int upper) {
        int[] pivotPoint = selectPivot(points, lower, upper);
        int pivotDistance = computeDistance(pivotPoint);
        while (lower < upper) {
            if (computeDistance(points[lower]) >= pivotDistance) {
                int[] temp = points[lower];
                points[lower] = points[upper];
                points[upper] = temp; 
                upper--;
            } else {
                lower++;
            }
        }
        
        if (computeDistance(points[lower]) < pivotDistance)
            lower++;
        return lower;
    }

    private int[] selectPivot(int[][] points, int lower, int upper) {
        return points[lower + (upper - lower) / 2];
    }
    
    private int computeDistance(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }
}

This Java solution tackles the problem of finding the k closest points to the origin in a given list of points that contains coordinates in a 2D plane. The approach employs the quickselect algorithm to efficiently solve the issue by partially sorting the points until the k closest are grouped at the beginning of the list.

To understand how this solution effectively achieves the goal:

• The kNearest method is the entry point that accepts the points array and the integer k. It delegates the task to a helper method selectKClosest.

• selectKClosest initializes two pointers (lower and upper) to manage the range of points to be processed and organizes the closest k points towards the beginning of the array. This is done through a partitioning process in which elements are rearranged based on their distance from the origin.

• The partitionPoints method works by selecting a pivot using the selectPivot method, arranging the points such that those with a distance less than the pivot's distance are moved to the left.

• computeDistance is a utility function to calculate the squared distance of a point from the origin, thus avoiding the computational expense of square root calculations.

At the completion of the process, the top k elements in the array are the desired closest points to the origin. These are returned after ensuring that the subsection of the points array containing the closest k points is separated out using Arrays.copyOf.

Ensure you appropriately choose the value of k to avoid bounds errors, as k must not exceed the length of the points array. This method efficiently handles the problem with a complexity that's generally better than sorting the entire array, making it suitable for large datasets.

var nearestKPoints = function(points, k) {
    return performQuickSelect(points, k)
};

var performQuickSelect = function(points, k) {
    let l = 0, r = points.length - 1
    let idx = points.length
    while (idx !== k) {
        // Applying partitioning on the points to find the k closest
        idx = selectPartition(points, l, r)
        if (idx < k) {
            l = idx
        } else {
            r = idx - 1
        }
    }
    
    // Extract the first k points from the array
    return points.slice(0, k)
};

var selectPartition = function(points, l, r) {
    let pivot = selectPivot(points, l, r)
    let dist = distanceSquared(pivot)
    while (l < r) {
        if (distanceSquared(points[l]) >= dist) {
           [points[l], points[r]] = [points[r], points[l]]
            r--
        } else {
            l++
        }
    }
    
    if (distanceSquared(points[l]) < dist)
        l++
    return l
};

const selectPivot = (points, l, r) => points[l + ((r - l) >> 1)]

const distanceSquared = ([x, y]) => x * x + y * y

The given JavaScript function nearestKPoints inputs an array of points and an integer k, then returns the k closest points to the origin (0, 0), utilizing the Quickselect algorithm.

• Process starts by invoking performQuickSelect, which is where the Quickselect algorithm is implemented.
• performQuickselect initializes boundaries (l for left and r for right) used to repeatedly partition the points array until the partition index idx matches k.
• selectPartition assists in this by choosing a pivot point and reordering the elements based on their squared distance from the origin; this distance is computed in distanceSquared.
• The array points is repeatedly partitioned: points closer to the origin than the pivot come before it, others after.
• The loop in performQuickSelect adjusts the values of l and r based on idx and k, effectively narrowing down the segment of the array to consider.
• Finally, the first k elements of the array, now the closest k points, are returned using .slice(0, k).

This method efficiently handles the selection of nearest points using spatial comparisons and minimizes the need to sort the entire array, thus optimizing performance especially for large datasets.

class Solver:
    def nearestKPoints(self, points: List[List[int]], k: int) -> List[List[int]]:
        return self.quickSelect(points, k)
    
    def quickSelect(self, points: List[List[int]], k: int) -> List[List[int]]:
        start, end = 0, len(points) - 1
        index = len(points)
        while index != k:
            index = self.partitionArray(points, start, end)
            if index < k:
                start = index
            else:
                end = index - 1
        return points[:k]
    
    def partitionArray(self, points: List[List[int]], start: int, end: int) -> int:
        pivotPoint = self.getMidpoint(points, start, end)
        pivotDist = self.calculateDist(pivotPoint)
        while start < end:
            if self.calculateDist(points[start]) >= pivotDist:
                points[start], points[end] = points[end], points[start]
                end -= 1
            else:
                start += 1
        if self.calculateDist(points[start]) < pivotDist:
            start += 1
        return start
    
    def getMidpoint(self, points: List[List[int]], start: int, end: int) -> List[int]:
        return points[start + (end - start) // 2]
    
    def calculateDist(self, point: List[int]) -> int:
        return point[0]**2 + point[1]**2

To identify the k closest points to the origin using your given set of points, the provided Python solution employs a class named Solver which integrates a Quickselect algorithm. Here’s a straightforward breakdown of how this implementation works:

1. Method Definitions

   • nearestKPoints(points, k): This is the entry method that takes a list of points and an integer k. It initializes the process by calling quickSelect with the same parameters.
   • quickSelect(points, k): Performs the Quickselect algorithm to find the k closest points. It works by partitioning the points list around a pivot so that points nearer to the origin are on one side of the pivot. The process repeats on the relevant partition until the partition size matches k.
   • partitionArray(points, start, end): Arranges the elements in the list such that those closer to the origin than the pivot are moved to the front of the list. This support method returns the new pivot index after partitioning.
   • getMidpoint(points, start, end): Selects the midpoint between start and end in the list as the pivot point.
   • calculateDist(point): Computes the distance of a point from the origin which is used to rank points in relation to the pivot.

2. Functionality

   • Begin by selecting the pivot using the midpoint of the list segment.
   • Calculate the Euclidean distance for the pivot and employ this distance to position other points relative to the pivot using partitionArray.
   • Continue refining the range (using start and end) and reselecting pivots until the section of points of interest narrows down to exactly k.

This solution is efficient, leveraging the O(n) average time complexity of the Quickselect algorithm, making it suitable for large datasets where sorting the entire list would be too costly.