JavaScript Coding Test Course, Finding the Kth Number in an Array

Coding tests are a very important element in modern software development. Companies issue various algorithm problems to evaluate developers’ problem-solving abilities. Today, we will address the problem of finding the Kth smallest number in an array. This problem is a good example to build basic algorithm skills in handling arrays.

Problem Description

Given an array arr and an integer k, find and return the Kth smallest number in arr. The array index starts from 0.

Input

• Integer array arr, length between 1 and 100,000.
• Integer k, between 1 and the length of the array.

Output

Return the Kth smallest number from arr.

Example

Solution Process

This problem can be easily solved by sorting the array first and then finding the Kth element, but the time complexity may vary depending on the sorting method. Here, we will explore two approaches.

Method 1: Sorting the array and finding the Kth number

1. Sort the array in ascending order.
2. Return the value at index k - 1 to find the Kth number.

JavaScript Code Example

function findKthNumber(arr, k) {
    arr.sort((a, b) => a - b); // Sort the array in ascending order
    return arr[k - 1]; // Return Kth number
}

// Example execution
console.log(findKthNumber([3, 1, 2, 4, 5], 2)); // 2
console.log(findKthNumber([7, 10, 4, 3, 20, 15], 3)); // 7

In the code above, we simply sorted the array and found the Kth element. The time complexity of this method is O(n log n). However, there is a way to find the Kth smallest number without necessarily sorting.

Method 2: Quickselect Algorithm

The Quickselect algorithm is a method to find the Kth smallest number in a way similar to Quicksort. This method has an average time complexity of O(n). This algorithm is performed by setting up a subarray and choosing a pivot.

1. Select a pivot element from the array.
2. Place values smaller than the pivot on the left and larger values on the right.
3. If the pivot’s position is the same as the position of the Kth number, return the pivot.
4. If not, perform Quickselect recursively in the appropriate subarray based on whether the Kth number is in the left or right subarray.

JavaScript Code Example

function quickSelect(arr, left, right, k) {
    if (left === right) {
        return arr[left]; // If there is only one element in the array
    }
    const pivotIndex = partition(arr, left, right);
    if (k === pivotIndex) {
        return arr[k]; // Kth number found
    } else if (k < pivotIndex) {
        return quickSelect(arr, left, pivotIndex - 1, k);
    } else {
        return quickSelect(arr, pivotIndex + 1, right, k);
    }
}

function partition(arr, left, right) {
    const pivot = arr[right]; // Select the last element as the pivot
    let i = left; 
    for (let j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]]; // Swap
            i++;
        }
    }
    [arr[i], arr[right]] = [arr[right], arr[i]]; // Final position of the pivot
    return i; // Return the index of the pivot
}

function findKthNumber(arr, k) {
    return quickSelect(arr, 0, arr.length - 1, k - 1); // Pass K-1 as the argument
}

// Example execution
console.log(findKthNumber([3, 1, 2, 4, 5], 2)); // 2
console.log(findKthNumber([7, 10, 4, 3, 20, 15], 3)); // 7

With the above code, we can efficiently find the Kth number using the Quickselect algorithm. This method is particularly useful for large datasets due to its average time complexity of O(n).

Conclusion

In this lecture, we explored the problem of finding the Kth number in an array, which is frequently covered in JavaScript coding tests. Although the problem can be solved simply with sorting, we can maximize performance by using efficient methods like Quickselect. Such knowledge can be very useful in actual coding tests, so I highly recommend practicing it.

All algorithms require a basic understanding followed by developing applicability through various problems. In the next lecture, we will cover more diverse array problems and advanced algorithms. Thank you!