Kth Smallest Element in Array 🎯

Welcome to our comprehensive guide on finding the Kth Smallest Element in an Array! This tutorial is designed to help both beginners and intermediates understand this important algorithmic concept. Let's dive right in!

What is the Kth Smallest Element? 📝

The Kth Smallest Element in an array is the Kth smallest number in the given array. This concept is useful in various real-world applications such as data analysis, sorting, and selection algorithms.

Algorithm Overview 💡

The algorithm we will be discussing is a modified QuickSelect algorithm, which is an efficient in-place variation of the QuickSort algorithm. It picks an element as pivot and partitions the array around the pivot such that all elements smaller than pivot come before it and all elements greater than pivot come after it. The Kth Smallest Element is found either in the pivot position or recursively in the appropriate half.

Pseudocode 💡

function kthSmallest(arr, k) {
    def quickSelect(arr, low, high) {
        if low < high {
            pivotIndex = partition(arr, low, high)
            if pivotIndex == k {
                return arr[pivotIndex]
            } else if pivotIndex > k {
                return quickSelect(arr, low, pivotIndex - 1)
            } else {
                return quickSelect(arr, pivotIndex + 1, high)
            }
        }
    }

    return quickSelect(arr, 0, arr.length - 1)
}

function partition(arr, low, high) {
    pivot = arr[high]
    i = low - 1
    for j from low to high - 1 {
        if arr[j] < pivot {
            i = i + 1
            swap(arr, i, j)
        }
    }
    swap(arr, i + 1, high)
    return i + 1
}

function swap(arr, i, j) {
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

Code Examples 💡

Example 1: Finding the 3rd smallest element in the array [12, 3, 5, 7, 1, 8, 2, 4, 6]

python

def kthSmallest(arr, k):
    def quickSelect(arr, low, high):
        if low < high:
            pivotIndex = partition(arr, low, high)
            if pivotIndex == k:
                return arr[pivotIndex]
            elif pivotIndex > k:
                return quickSelect(arr, low, pivotIndex - 1)
            else:
                return quickSelect(arr, pivotIndex + 1, high)

    return quickSelect(arr, 0, len(arr) - 1)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

arr = [12, 3, 5, 7, 1, 8, 2, 4, 6]
k = 3
print(kthSmallest(arr, k))  # Output: 3

Example 2: Finding the 5th smallest element in the array [100, 5, 1, 2, 8, 3, 6, 4]

python

def kthSmallest(arr, k):
    def quickSelect(arr, low, high):
        if low < high:
            pivotIndex = partition(arr, low, high)
            if pivotIndex == k:
                return arr[pivotIndex]
            elif pivotIndex > k:
                return quickSelect(arr, low, pivotIndex - 1)
            else:
                return quickSelect(arr, pivotIndex + 1, high)

    return quickSelect(arr, 0, len(arr) - 1)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

arr = [100, 5, 1, 2, 8, 3, 6, 4]
k = 5
print(kthSmallest(arr, k))  # Output: 1

Quiz 💡

Conclusion ✅

Congratulations on mastering the Kth Smallest Element concept! You've learned the algorithm, pseudocode, and practical implementation examples. Practice these examples and try applying this algorithm to your own projects. Keep exploring, and happy coding! 🚀🌟