Problem Statement
Given an array arr[] and an integer k, find the kth smallest element in the array.
The kth smallest element is based on the sorted order of the array.
Examples
Input: arr = [10, 5, 4, 3, 48, 6, 2, 33, 53, 10], k = 4
Output: 5
Input: arr = [7, 10, 4, 3, 20, 15], k = 3
Output: 7
Objective
• Sort the array (or logically determine order)
• Return the element at position k-1
________________________________________Approach 1: Sorting Method (Simple & Clear)
Idea
• Sort the array in ascending order
• The kth smallest element will be at index k-1
Python Code
arr = [10, 5, 4, 3, 48, 6, 2, 33, 53, 10]
k = 4
arr.sort()
print(arr[k-1])
Step-by-Step
Original array:
[10, 5, 4, 3, 48, 6, 2, 33, 53, 10]
Sorted array:
[2, 3, 4, 5, 6, 10, 10, 33, 48, 53]
4th smallest → index 3 → 5
Complexity
• Time: O(n log n) (due to sorting)
• Space: O(1)
Approach 2: Using Heap (Efficient)
Idea
• Use a min heap
• Extract the smallest element k times
Python Code
import heapq
arr = [10, 5, 4, 3, 48, 6, 2, 33, 53, 10]
k = 4
heapq.heapify(arr)
for _ in range(k-1):
heapq.heappop(arr)
print(heapq.heappop(arr))
Complexity
• Time: O(n + k log n)
• Space: O(1)
Approach 3: Using Built-in Function
arr = [7, 10, 4, 3, 20, 15]
k = 3
print(sorted(arr)[k-1])
Edge Cases
• k = 1 → smallest element
• k = n → largest element
• Duplicate values → still count separately
• Large input size
Final Thoughts
• Sorting is the simplest approach
• Heap is better for performance optimization
• This problem is important for understanding:
o Sorting
o Heaps
o Selection algorithms
Top comments (0)