Find Kth Smallest Element using Quickselect - Visualization

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given an unsorted array of integers and a number k, your task is to find the kth 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.

Examples❯

Input Array k Output Description
[7, 10, 4, 3, 20, 15] 3 7 The 3rd smallest element is 7Visualization
[7, 10, 4, 3, 20, 15] 4 10 The 4th smallest element is 10Visualization
[1] 1 1 Single element, return it directlyVisualization
[9, 8, 7, 6] 1 6 Smallest element is 6Visualization
[5, 3, 2, 4, 1] 5 5 Largest element (k = n)Visualization
[2, 1] 3 -1 k exceeds array lengthVisualization
[] 1 -1 Empty array, return error or -1Visualization

Solution❯

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!

Algorithm Steps❯

  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).

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

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

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)If the pivot divides the array evenly, each recursive call reduces the problem size by half, leading to linear time complexity.
Average CaseO(n)On average, the random pivot leads to a fairly balanced partition, resulting in linear time complexity for finding the kth element.
Worst CaseO(n²)In the worst case (e.g., when the smallest or largest element is always chosen as pivot), the partitioning is highly unbalanced, resulting in quadratic time complexity.

Space Complexity❯

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

Explanation: 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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...