Find Kth Smallest Element using Quickselect

Contents

ProblemExamplesVisualizationSolutionAlgorithmCodeTimeSpace

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

Visualization Player

Solution❯

The Quickselect algorithm is a powerful tool to find the kth smallest element in an unsorted array without fully sorting it. It works efficiently in most cases, running in O(n) average time.

Understanding the Goal

If you were to sort the array, the kth smallest element would be at index k - 1. But full sorting takes O(n log n) time. Quickselect helps us get the answer without sorting everything.

How It Works

The algorithm works by choosing a pivot (often randomly) and partitioning the array into three groups:

  • Lows: all elements less than the pivot
  • Pivots: all elements equal to the pivot
  • Highs: all elements greater than the pivot

Now, depending on the size of these groups, we decide where to continue:

  • If k is less than or equal to the size of lows, then the answer lies in the lows part, and we recursively apply Quickselect there.
  • If k falls within the size of lows + pivots, then the pivot is the kth smallest number—we return it directly.
  • Otherwise, we look into highs, subtracting the size of lows and pivots from k because we’ve skipped over that many smaller elements.

Handling Special Cases

  • If the array is empty or k < 1, return -1 because there's no valid answer.
  • If k is larger than the number of elements in the array, we should also return -1 to indicate it's out of bounds.
  • If the array contains duplicates, the algorithm still works since it accounts for equal-to-pivot elements as a separate group.
  • If the array has only one element, and k = 1, that single element is the answer.

This approach avoids the overhead of full sorting and gives us just the answer we need by narrowing our focus each time.

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

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
import random

def quickselect(arr, k):
    if len(arr) == 1:
        return arr[0]
    pivot = random.choice(arr)
    lows = [x for x in arr if x < pivot]
    highs = [x for x in arr if x > pivot]
    pivots = [x for x in arr if x == pivot]
    if k <= len(lows):
        return quickselect(lows, k)
    elif k <= len(lows) + len(pivots):
        return pivot
    else:
        return quickselect(highs, k - len(lows) - len(pivots))

if __name__ == '__main__':
    arr = [7, 10, 4, 3, 20, 15]
    k = 3
    print("The", k, "th smallest element is:", quickselect(arr, k))

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.