K Closest Points [WIP]

quick_select_attempt.js

let distanceMemo = new Map();

var kClosest = function(points, K) {
    // Choose pivot
    // pseudo sort all items around pivot
    // Get new partition position
    //  If K is larger, do again with a pivot in smaller section
    //      vice versa
    
    let left = 0;
    let right = points.length - 1;
    
    let pivot, lastPivot;
    let partitionIndex;
    let targetIndex = K - 1;
    let checkedPartitions = {};
    console.log(points.map((point, i) => distance(i)))
    
    while (partitionIndex !== targetIndex) { // left <= right && 
        if (left >= right) console.log('there was a problem, left > right');
        
        pivot = Math.floor((left + right) / 2);
        partitionIndex = partition(pivot, left, right);
        
        if (partitionIndex > targetIndex) {
            right = partitionIndex - 1;
        } else if (partitionIndex < targetIndex) {
            left = partitionIndex + 1;
        }
        console.log(pivot, 'after partition:', JSON.stringify(points));
    }
    
    return points.slice(0, K);

    function partition (pivot, left, right) {
        const pivotVal = distance(pivot);


        while (left <= right) {
            while (distance(left) < pivotVal) {
                left++;
            }

            while (distance(right) > pivotVal) {
                right--;
            }

            if (distance(left) === distance(right)) return left;

            // Swap points if still valid
            if (left < right) {
                swap(left, right);

                left++;
                right--;
            }
        }
        swap(pivot, right);

        return left;
    }
    
    function swap (left, right) {
        const temp = points[left];
        points[left] = points[right];
        points[right] = temp;
    }

    function distance (index) {
        const point = points[index];
        const key = `${point[0]}${point[1]}`;

        if (distanceMemo.has(key)) return distanceMemo.get(key);

        const distance = point[0] ** 2 + point[1] ** 2;
        distanceMemo.set(key, distance);
        return distance;
    }
};

Not working yet. Problem around pivot/partition scheme.

Currently using middle of left/right as new pivot based on last partition.
Somehow missing some values at end of the array.