Kth Smallest Element in an Array

Introduction
In data structures and algorithms, finding the kth smallest element in an array is a commonly asked problem. It helps in understanding sorting techniques and efficient data processing methods.

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

Example
Input:
arr = [10, 5, 4, 3, 48, 6, 2, 33, 53, 10]
k = 4
Output:
5
Explanation:
After sorting the array:

[2, 3, 4, 5, 6, 10, 10, 33, 48, 53]

The 4th smallest element is 5.

Approach 1: Using Sorting
Explanation

The simplest approach is to sort the array in ascending order and return the element at index k-1.

Python Code
class Solution:
def kthSmallest(self, arr, k):
arr.sort()
return arr[k-1]

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

Approach 2: Using Heap

Explanation
A more efficient method for large datasets is to use a min-heap. This avoids sorting the entire array and improves performance.

Python Code
import heapq

class Solution:
def kthSmallest(self, arr, k):
return heapq.nsmallest(k, arr)[-1]

Complexity
Time Complexity: O(n log k)
Space Complexity: O(k)

When to Use Each Approach

Sorting is suitable for smaller inputs or when simplicity is preferred.
Heap is better for large datasets where performance matters.

Conclusion

The kth smallest element problem can be solved using multiple approaches. Sorting provides a simple solution, while heap-based methods offer better efficiency for larger datasets. Understanding both approaches is important for coding interviews and real-world applications.