kth Smallest

Introduction

Arrays are widely used in programming, and many problems involve sorting and selection.
One important problem is finding the kth smallest element, which helps in understanding sorting and ranking concepts.

This problem is commonly asked in coding interviews and competitive programming.

Problem Statement

Given an integer array arr[] and an integer k,
find and return the kth smallest element in the array.

Note: The kth smallest element is determined based on the sorted order of the array.

Examples

Example 1:
Input: arr = [10, 5, 4, 3, 48, 6, 2, 33, 53, 10], k = 4
Output: 5

Explanation:
Sorted array → [2, 3, 4, 5, 6, 10, 10, 33, 48, 53]
4th smallest element = 5

Example 2:
Input: arr = [7, 10, 4, 3, 20, 15], k = 3
Output: 7

Explanation:
Sorted array → [3, 4, 7, 10, 15, 20]
3rd smallest element = 7

Intuition

If we sort the array in ascending order, the kth smallest element will be at index k-1.
However, sorting the entire array is not always efficient for large inputs.

Approach 1: Sorting (Basic Method)

• Sort the array
• Return element at index k-1

Code (Python - Sorting)

def kth_smallest(arr, k):
    arr.sort()
    return arr[k - 1]

Complexity (Sorting)

• Time Complexity: O(n log n)
• Space Complexity: O(1)

Approach 2: Optimized (QuickSelect Algorithm)

Instead of sorting the entire array, we use QuickSelect, which is based on QuickSort.

• Choose a pivot element
• Partition the array into:
  • Smaller elements
  • Larger elements
• Place pivot in correct position
• Check:
  • If pivot index == k-1 → return answer
  • If pivot index > k-1 → search left
  • If pivot index < k-1 → search right

Code (Python - QuickSelect)

def quickselect(arr, left, right, k):
    if left <= right:
        pivot = arr[right]
        p_index = left

        for i in range(left, right):
            if arr[i] <= pivot:
                arr[i], arr[p_index] = arr[p_index], arr[i]
                p_index += 1

        arr[p_index], arr[right] = arr[right], arr[p_index]

        if p_index == k - 1:
            return arr[p_index]
        elif p_index > k - 1:
            return quickselect(arr, left, p_index - 1, k)
        else:
            return quickselect(arr, p_index + 1, right, k)

def kth_smallest(arr, k):
    return quickselect(arr, 0, len(arr) - 1, k)

Step-by-Step Explanation

• Pick a pivot
• Rearrange elements around pivot
• Check pivot position
• Reduce search space each time

Complexity (QuickSelect)

• Average Time Complexity: O(n)
• Worst Case: O(n²) (rare)
• Space Complexity: O(1)

Why is QuickSelect Better?

• No need to fully sort the array
• Faster for large datasets
• Reduces unnecessary computations

Conclusion

Finding the kth smallest element is a fundamental problem that introduces both basic and advanced techniques.
While sorting is easy to implement, QuickSelect provides an efficient optimized solution for large inputs.