Find Kth Smallest Element

Given an unsorted array of integers and a number k, your task is to find the k^th smallest element in the array using an efficient technique.

• k is 1-based, meaning k = 1 refers to the smallest element, k = 2 refers to the second smallest, and so on.
• If k is larger than the number of elements in the array, return -1 or indicate that it is out of bounds.

This problem can be solved in linear average time using the Quickselect algorithm, which is related to Quicksort but optimized to find a specific order statistic without full sorting.

Understanding the Problem

We are given an unsorted array and a number k. Our goal is to find the kth smallest element in the array.

Let’s understand this with an example:

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

If we sorted the array, it would become: [3, 4, 7, 10, 15, 20]. The 3rd smallest element is 7.

But sorting the entire array takes O(n log n) time. We want to find the answer more efficiently.

Approach: Quickselect Algorithm

The Quickselect algorithm helps us find the kth smallest element in average O(n) time — without sorting the whole array.

How Quickselect Works

We follow these steps:

1. Choose a pivot element from the array (usually random).
2. Partition the array into three parts:
   • lows: elements less than the pivot
   • pivots: elements equal to the pivot
   • highs: elements greater than the pivot
3. Now compare k with the sizes of these parts:
   • If k ≤ size of lows, then the answer lies in the lows part. Recur on that.
   • If k ≤ size of lows + size of pivots, the pivot itself is the kth smallest element.
   • Else, the answer lies in the highs part. Recur on highs with k - size of lows - size of pivots.

Let’s Visualize With the Same Example

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

• Choose pivot = 7
• Partition: lows = [4, 3], pivots = [7], highs = [10, 20, 15]
• lows has 2 elements, pivots has 1 → total = 3
• Since k = 3 is within (2 + 1), return pivot = 7

Handling Edge Cases

Case 1: Empty array

If the input array is empty, there's no element to find. Return -1.

Case 2: k is out of bounds

If k < 1 or k > length of array, return -1.

Case 3: Array has duplicates

The algorithm works even if duplicates exist because it separates values equal to the pivot.

Case 4: Array has one element

If the array has only one value and k = 1, then return that element directly.

Why This Is Efficient

Unlike full sorting, which looks at every element multiple times, Quickselect repeatedly focuses only on the part of the array where the answer could be. This smart narrowing saves time.

That’s how we solve the problem of finding the kth smallest element — step by step, clearly and efficiently!

1. Given an array of numbers and an integer k (1-indexed), the goal is to find the kth smallest element.
2. If the array contains only one element, return that element.
3. Randomly choose a pivot from the array.
4. Partition the array into three groups: lows (elements less than the pivot), pivots (elements equal to the pivot), and highs (elements greater than the pivot).
5. If k is less than or equal to the size of lows, recursively search in lows.
6. If k is within the size of lows plus pivots, the pivot is the kth smallest element.
7. Otherwise, recursively search in highs with an updated k (subtracting the sizes of lows and pivots).

#include <stdio.h>
#include <stdlib.h>

int main() {
    int a = 10, b = 20;
    int sum = a + b;
    printf("Sum: %d\n", sum);
    return 0;
}

#include <iostream>
using namespace std;

int main() {
    int a = 10, b = 20;
    cout << "Sum: " << (a + b) << endl;
    return 0;
}

def add(a, b):
    return a + b

if __name__ == '__main__':
    a, b = 10, 20
    print("Sum:", add(a, b))

public class Main {
    public static void main(String[] args) {
        int a = 10, b = 20;
        int sum = a + b;
        System.out.println("Sum: " + sum);
    }
}

function add(a, b) {
    return a + b;
}

let a = 10, b = 20;
console.log("Sum:", add(a, b));

package main
import "fmt"

func main() {
    a, b := 10, 20
    sum := a + b
    fmt.Println("Sum:", sum)
}

fn main() {
    let a = 10;
    let b = 20;
    let sum = a + b;
    println!("Sum: {}", sum);
}

fun main() {
    val a = 10
    val b = 20
    val sum = a + b
    println("Sum: $sum")
}

import Foundation

let a = 10
let b = 20
let sum = a + b
print("Sum: \(sum)")

function add(a: number, b: number): number {
    return a + b;
}

let a = 10, b = 20;
console.log("Sum:", add(a, b));

Time complexity

Space complexity

O(1) (in-place) or O(n) (with extra arrays)

If implemented in-place like Lomuto partition, it uses constant space. But if implemented with extra arrays for lows, pivots, and highs, it uses linear space.