Finding the Kth Smallest Element in an Array - CA07

Introduction

In many real-world problems, we are not just interested in the smallest or largest element, but in a specific position when the data is sorted. One such common problem is finding the kth smallest element in an array.

Problem Statement

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

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

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]
The 4th smallest element is 5.

Example 2:

Input:

arr = [7, 10, 4, 3, 20, 15]
k = 3

Output:

7

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

Approach 1: Sorting Method

The simplest way is:

1. Sort the array
2. Return the element at index k-1

Python Implementation

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

# Example usage
arr = [7, 10, 4, 3, 20, 15]
k = 3
print(kth_smallest(arr, k))

Approach 2: Using Min Heap

A more efficient method for large data:

1. Convert the array into a min heap
2. Extract the smallest element k times

Python Implementation

import heapq

def kth_smallest(arr, k):
    heapq.heapify(arr)

    for _ in range(k - 1):
        heapq.heappop(arr)

    return heapq.heappop(arr)

# Example usage
arr = [7, 10, 4, 3, 20, 15]
k = 3
print(kth_smallest(arr, k))

Conclusion

Finding the kth smallest element helps in understanding sorting and priority-based problems. While sorting is sufficient for beginners, using heaps introduces more efficient techniques for handling large datasets.

Mastering this problem builds a strong foundation for more advanced algorithms.