Kth smallest element in an array

Problem Understanding

We are given an array and a number k.
We need to find the k-th smallest element.

Example:
arr = [10, 5, 4, 3, 48], k = 2
Sorted → [3, 4, 5, 10, 48]
Answer → 4

**Common Approach (Not Best)

Sorting
sorted(arr)[k-1]
Time: O(n log n)
We sort the whole array (unnecessary)
**
** Best Approach: QuickSelect**
Idea

Similar to QuickSort
Pick a pivot
Place pivot in its correct position
Only search one side (not both!)

Code (Short & Optimal)

import random
class Solution:
    def kthSmallest(self, arr, k):
        def select(l, r):
            pivot = arr[random.randint(l, r)]
            i, j = l, r

            while i <= j:
                while arr[i] < pivot: i += 1
                while arr[j] > pivot: j -= 1
                if i <= j:
                    arr[i], arr[j] = arr[j], arr[i]
                    i += 1
                    j -= 1

            if k-1 <= j: return select(l, j)
            if k-1 >= i: return select(i, r)
            return arr[k-1]
        return select(0, len(arr)-1)

Line-by-Line Explanation

pivot = arr[random.randint(l, r)]
We pick a random pivot
Why?

Avoid worst-case (O(n²))
i, j = l, r
Two pointers:
i → left side
j → right side
Partition Logic
while i <= j:
    while arr[i] < pivot: i += 1
    while arr[j] > pivot: j -= 1
Move i → until element ≥ pivot
Move j → until element ≤ pivot
Swapping
if i <= j:
    arr[i], arr[j] = arr[j], arr[i]
Put smaller elements left
Larger elements right

Decide Direction
if k-1 <= j: return select(l, j)
if k-1 >= i: return select(i, r)

This is the MOST IMPORTANT PART

If k-th element is in left part → go left
If in right part → go right
Else → found answer

Why QuickSelect is Better

1. No full sorting → finds only k-th element
2. Searches one side only → less work
3. Faster → O(n) (better than O(n log n))
4. No extra space → O(1)
5. Good for large arrays