How to use Quick Select In Javascript

In this approach, Implement the Quick Select algorithm to find the K-th smallest element in an array. Modify the algorithm to handle the removal of integers that do not meet the specified condition. Use the modified Quick Select algorithm to find the K-th smallest integer after removing the specified integers from the natural numbers

Example: The example below shows how to find the K-th smallest element after removing some integers from natural numbers using Quick Select.

JavaScript

function partition(arr, left, right, pivotIndex) {
    const pivotValue = arr[pivotIndex];
    let storeIndex = left;

    // Move pivot to the end
    [arr[pivotIndex], arr[right]] = 
            [arr[right], arr[pivotIndex]];

    // Partition the array
    for (let i = left; i < right; i++) {
        if (arr[i] < pivotValue) {
            [arr[i], arr[storeIndex]] =
                    [arr[storeIndex], arr[i]];
            storeIndex++;
        }
    }

    // Move pivot to its final place
    [arr[right], arr[storeIndex]] = 
            [arr[storeIndex], arr[right]];
    return storeIndex;
}

function quickSelect(arr, left, right, k) {
    while (left <= right) {
        const pivotIndex = Math.floor(Math.random() *
                                (right - left + 1)) + left;
        const partitionIndex =
            partition(arr, left, right, pivotIndex);

        if (partitionIndex === k) {
            return arr[partitionIndex];
        } else if (partitionIndex < k) {
            left = partitionIndex + 1;
        } else {
            right = partitionIndex - 1;
        }
    }
}

function kthSmallestAfterRemoval(arr, k, MAX) {
    const remainingNumbers = [];
    let num = 1;

    while (remainingNumbers.length < k) {
        if (!arr.includes(num)) {
            remainingNumbers.push(num);
        }
        num++;
    }

    return quickSelect(remainingNumbers, 0,
                            remainingNumbers.length - 1, k - 1);
}

const arr = [3, 5];
const k = 2;
const MAX = 10;
console.log("K-th smallest element after removal:",
                    kthSmallestAfterRemoval(arr, k, MAX));

Output

K-th smallest element after removal: 2

Time complexity: O(n)

Space complexity: O(k)

K-th Smallest Element after Removing some Integers from Natural Numbers using JavaScript

Given an array of size “n” and a positive integer k our task is to find the K-th smallest element that remains after removing certain integers from the set of natural numbers using JavaScript.

Example:

Input: array = [3, 5]
k = 2

Output: 2

Explanation: The natural numbers are [1, 2, 3, 4, 5......]  and after removing elements 3 and 5 from the natural numbers, the remaining numbers are [1, 2, 4....]. 
The 2nd smallest number from the remaining numbers is 2.

Below are the approaches to finding the K-th smallest element after removing some integers from natural numbers using JavaScript:

Table of Content

Brute Force approach
Using Quick Select
Flag and Counting Approach
Using Sets

How to use Quick Select In Javascript

K-th Smallest Element after Removing some Integers from Natural Numbers using JavaScript

Example:

Similar Reads