Learning Journal

2/20/2024

Top K Frequent Elements

function topKFrequent(nums: number[], k: number): number[] {
    const hashTB: Record<string,number> = {};

    for(let i = 0; i < nums.length; i++) {
        if(hashTB[nums[i]] === undefined)
            hashTB[nums[i]] = 1;
        else 
            hashTB[nums[i]]++;
    }

    const keyArr = Object.keys(hashTB);

    if(keyArr.length <= k) return keyArr.map(Number);

    shuffle(keyArr);

    
    let pivotI = 0, lo = 0, hi = keyArr.length - 1;
    
    while(pivotI !== k) {
        pivotI = partition(lo, hi);

        if(pivotI < k) {
            lo = pivotI + 1;
        }
        else if(pivotI > k){
            hi = pivotI - 1;
        }

    }

    return keyArr.slice(0, pivotI).map(Number);


    function partition(lo:number, hi:number):number {
        let leftP = lo+1, rightP = hi, pivotI = lo;

        while(true) {
            while(leftP <= hi && hashTB[keyArr[leftP]] >= hashTB[keyArr[pivotI]]) {
                leftP++;
            }

            if(leftP > hi) break;

            while(hashTB[keyArr[rightP]] < hashTB[keyArr[pivotI]]){
                rightP--;
            }

            if(rightP < leftP) break;

            swap(keyArr, leftP, rightP);
        }

        if(rightP !== pivotI) swap(keyArr, rightP, pivotI);

        return rightP;
    }


};


function swap(arr:any[], i1:number, i2:number) {
    const temp = arr[i1];
    arr[i1] = arr[i2];
    arr[i2] = temp;

}


function shuffle(arr:any[]) {
    for(let i = arr.length - 1; i >= 0; i--){
        const newI = Math.floor(Math.random()* (i + 1));

        const temp = arr[i];
        arr[i] = arr[newI];
        arr[newI] = temp;
    }
}

function topKFrequent(nums: number[], k: number): number[] {
    const hashTB: Record<string,number> = {};

    for(let i = 0; i < nums.length; i++) {
        if(hashTB[nums[i]] === undefined)
            hashTB[nums[i]] = 1;
        else 
            hashTB[nums[i]]++;
    }

    const keyArr = Object.keys(hashTB);

    if(keyArr.length <= k) return keyArr.map(Number);

    shuffle(keyArr);

    
    let pivotI = 0, lo = 0, hi = keyArr.length - 1;
    
    while(pivotI !== k) {
        pivotI = partition(lo, hi);

        if(pivotI < k) {
            lo = pivotI + 1;
        }
        else if(pivotI > k){
            hi = pivotI - 1;
        }

    }

    return keyArr.slice(0, pivotI).map(Number);


    function partition(lo:number, hi:number):number {
        let leftP = lo+1, rightP = hi, pivotI = lo;

        while(true) {
            while(leftP <= hi && hashTB[keyArr[leftP]] >= hashTB[keyArr[pivotI]]) {
                leftP++;
            }

            if(leftP > hi) break;

            while(hashTB[keyArr[rightP]] < hashTB[keyArr[pivotI]]){
                rightP--;
            }

            if(rightP < leftP) break;

            swap(keyArr, leftP, rightP);
        }

        if(rightP !== pivotI) swap(keyArr, rightP, pivotI);

        return rightP;
    }


};


function swap(arr:any[], i1:number, i2:number) {
    const temp = arr[i1];
    arr[i1] = arr[i2];
    arr[i2] = temp;

}


function shuffle(arr:any[]) {
    for(let i = arr.length - 1; i >= 0; i--){
        const newI = Math.floor(Math.random()* (i + 1));

        const temp = arr[i];
        arr[i] = arr[newI];
        arr[newI] = temp;
    }
}

THE PROBLEM

The quickselect approach for this problem is interesting. You don't need to sort the whole array, you just need to find the element at k-th position. That's all. Because you know that k elements before it (from index 0 to index k-1), regardless of their order, are the k largest elements in the array.

Another interesting observation is that the right pointer is always the one you should return from the partition function of quick sort.

Why? Because you move it after the left pointer.

Let me break it down a little bit more.

At the moment right before the left pointer starts to move, there are 2 cases: first, it is the first iteration, and second, it is not.

When it is not the first iteration, which means the right pointer already moves at the previous iteration, and because of that, the element that is currently pointed by the right pointer is less than the pivot element. So, the left pointer can move at most to the right pointer and stop, then the right pointer will move 1 step to the left, encounter the element that is greater or equal to the pivot and stop. That is the first element that is greater or equal to the pivot, and thus, it is the pivot position.

When it is the first iteration, which means the right pointer has not moved yet. Because of that, it can point to the element that is greater or equal to the pivot, and thus the left pointer can go pass it and reaches hi + 1 (the right pointer is pointing to hi). At this time, the while loop stops and the right pointer is pointing to the last element in the array that has all elements greater or equal to pivot, thus, the pivot should be at the right pointer position./

Revised by ChatGPT

The quickselect approach for this problem is efficient because you don't need to sort the entire array; you only need to find the element at the k-th position. This ensure that the k elements before it (from index 0 to index k-1) are the k largest elements in the array, regardless of their order.

An important detail in the implementation is the use of the right pointer as the return value from the partition function. This works in this specific case because of the way the partitioning is done, but it's not a general rule for all quickselect or quicksort algorithms.

Here's a breakdown of why the right pointer is returned in this implementation:

Non-First Iteration: If it's not the first iteration, it means the right pointer has already moved in a previous iteration. Therefore, the element at the right pointer is less than the pivot. As the left pointer moves, it can, at most, reach the right pointer's position and stop. Then, the right pointer moves one step to the left, encounters an element that is greater than or equal to the pivot and stops. This position is the first element that is greater than or equal to the pivot, indicating the correct position for the pivot.
First Iteration: If the while loop stops at the first iteration, it means that the left pointer has moved past the right pointer while the right pointer has not moved yet. This indicates that all elements from the pivot's position to the right pointer's position are greater than or equal to the pivot. Therefore, the pivot should be placed at the right pointer's position, as it is the last element in this range that satisfies this condition.