🧠 Kth Smallest Element in an Array – Python

Hi All,

Today I solved an important problem: 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 based on the sorted order of the array.

---

🔍 Examples

Example 1:

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

Output:

5

---

Example 2:

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

Output:

7

---

💡 Approach

🔹 Method 1: Sorting (Simple)

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

👉 Easy but not optimal for large inputs

---

💻 Python Code (Sorting)

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

---

🔹 Method 2: Min Heap (Optimal)

👉 Best approach for this problem

• Use a heap (priority queue)
• Extract smallest elements k times

---

💻 Python Code (Heap)

import heapq

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

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

    return heapq.heappop(arr)

---

🔍 Dry Run

For:

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

Steps:

• Heap → [3, 7, 4, 10, 20, 15]
• Remove 1st smallest → 3
• Remove 2nd smallest → 4
• Next smallest → 7

Final Output:

7

---

🖥️ Sample Output

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

---

⚡ Complexity Analysis

Method	Time Complexity	Space
Sorting	O(n log n)	O(1)
Heap	O(n log k)	O(k) ✅

---

🧠 Explanation

• Sorting → simplest method
• Heap → more efficient for large arrays
• Heap keeps smallest elements at top
• We remove elements until we reach kth smallest

---

✅ Conclusion

This problem helped me understand:

• Sorting vs Heap optimization
• Priority Queue (Heap) usage
• Efficient selection algorithms

🚀 Very important for coding interviews!

---