🎯 Find the Kth Smallest Element in an Array

Finding the kth smallest element is a common and important problem in data structures and algorithms.
It appears frequently in coding interviews and competitive programming.

---

📌 Problem Statement

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

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

---

🔍 Examples

Example 1:

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

Example 2:

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

---

🧠 Concept

If we sort the array, the kth smallest element will be at index:

k - 1

But sorting takes O(n log n) time.

👉 We can do better using a Heap (Priority Queue).

---

🔄 Approach: Using Max Heap (Efficient)

We maintain a max heap of size k.

Step-by-Step:

1. Create an empty max heap
2. Iterate through the array:

• Add element to heap

• If heap size > k → remove the largest element

  1. After processing all elements:

• The root of heap = kth smallest element

---

💻 Python Code (Heap)

```python id="w7o3ka"
import heapq

def kth_smallest(arr, k):
max_heap = []

for num in arr:
    heapq.heappush(max_heap, -num)  # use negative for max heap

    if len(max_heap) > k:
        heapq.heappop(max_heap)

return -max_heap[0]

Example

print(kth_smallest([7, 10, 4, 3, 20, 15], 3))

---

## 🧾 Dry Run (Step-by-Step)

For:



```id="s9xzq7"
arr = [7, 10, 4, 3, 20, 15], k = 3

Heap process:

• Add 7 → [7]
• Add 10 → [10, 7]
• Add 4 → [10, 7, 4]
• Add 3 → remove 10 → [7, 4, 3]
• Add 20 → remove 20 → [7, 4, 3]
• Add 15 → remove 15 → [7, 4, 3]

👉 Answer = 7

---

⚡ Time and Space Complexity

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

---

🔁 Alternative Approach: Sorting

```python id="j18s6n"
def kth_smallest(arr, k):
arr.sort()
return arr[k - 1]

* Time: `O(n log n)`
* Simpler but less efficient

---

## 🚀 Bonus: Quickselect (Advanced)

* Average Time: `O(n)`
* Worst Case: `O(n²)`
* Used in advanced interview questions

---

## 🧩 Where Is This Used?

* Order statistics
* Data analysis
* Ranking systems
* Interview problems

---

## 🏁 Conclusion

The **max heap approach** is the most efficient and widely used method when dealing with kth smallest problems under constraints.