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.Most sorting algorithms work only when the array is sorted.

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 #Data Structure(min-heap)

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.