Problem

Given an integer array nums and an integer k, return the kth smallest element in the array.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Examples

Example 1

1
2
3

Input: nums = [3,2,1,5,6,4], k = 2
Output: 2
Explanation: The sorted array is [1,2,3,4,5,6], so the 2nd smallest is 2.

Example 2

1
2
3

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 3
Explanation: The sorted array is [1,2,2,3,3,4,5,5,6], so the 4th smallest is 3.

Similar Problems

Solution

There are several ways to solve this problem. Here are some common approaches:

Method 1 – Bubble K Times

Intuition

This method is based on the idea of partially sorting the array using bubble sort, but only for the first k passes, so that the k smallest elements bubble to the front.

Approach

  1. Run the outer loop of bubble sort for k times.
  2. After k passes, the first k elements will be the k smallest (not necessarily sorted).
  3. Return the k-th element from the front.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int findKthSmallest(vector<int>& nums, int k) {
        int n = nums.size();
        for (int i = 0; i < k; ++i) {
            for (int j = 0; j < n - i - 1; ++j) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums[j], nums[j + 1]);
                }
            }
        }
        return nums[k - 1];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func findKthSmallest(nums []int, k int) int {
    n := len(nums)
    for i := 0; i < k; i++ {
        for j := 0; j < n-i-1; j++ {
            if nums[j] > nums[j+1] {
                nums[j], nums[j+1] = nums[j+1], nums[j]
            }
        }
    }
    return nums[k-1]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int findKthSmallest(int[] nums, int k) {
        int n = nums.length;
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        return nums[k - 1];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun findKthSmallest(nums: IntArray, k: Int): Int {
        val n = nums.size
        for (i in 0 until k) {
            for (j in 0 until n - i - 1) {
                if (nums[j] > nums[j + 1]) {
                    val temp = nums[j]
                    nums[j] = nums[j + 1]
                    nums[j + 1] = temp
                }
            }
        }
        return nums[k - 1]
    }
}
1
2
3
4
5
6
7

def find_kth_smallest(nums: list[int], k: int) -> int:
    n = len(nums)
    for i in range(k):
        for j in range(n - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums[k - 1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn find_kth_smallest(nums: &mut Vec<i32>, k: i32) -> i32 {
        let n = nums.len();
        for i in 0..k as usize {
            for j in 0..n - i - 1 {
                if nums[j] > nums[j + 1] {
                    nums.swap(j, j + 1);
                }
            }
        }
        nums[(k - 1) as usize]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    findKthSmallest(nums: number[], k: number): number {
        const n = nums.length;
        for (let i = 0; i < k; i++) {
            for (let j = 0; j < n - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
                }
            }
        }
        return nums[k - 1];
    }
}

Complexity

  • ⏰ Time complexity: O(nk), because for each of the k passes, we may compare up to n elements.
  • 🧺 Space complexity: O(1), as sorting is done in-place and no extra space is used.

Method 2 – Temporary Array of Size K

Intuition

Keep a temporary array of size k to store the k smallest elements found so far, always maintaining the largest among them for replacement.

Approach

  1. Copy the first k elements into a temporary array.
  2. For each remaining element, if it is smaller than the largest in the temp array, replace the largest.
  3. After processing, the largest in temp is the kth smallest.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int findKthSmallest(vector<int>& nums, int k) {
        priority_queue<int> maxHeap;
        for (int i = 0; i < k; ++i) {
            maxHeap.push(nums[i]);
        }
        for (int i = k; i < nums.size(); ++i) {
            if (nums[i] < maxHeap.top()) {
                maxHeap.pop();
                maxHeap.push(nums[i]);
            }
        }
        return maxHeap.top();
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

func findKthSmallest(nums []int, k int) int {
    if k <= 0 || k > len(nums) {
        return 0
    }
    maxHeap := &IntHeap{}
    heap.Init(maxHeap)
    for i := 0; i < k; i++ {
        heap.Push(maxHeap, nums[i])
    }
    for i := k; i < len(nums); i++ {
        if nums[i] < (*maxHeap)[0] {
            heap.Pop(maxHeap)
            heap.Push(maxHeap, nums[i])
        }
    }
    return (*maxHeap)[0]
}

// IntHeap is a type that implements heap.Interface for a slice of integers.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] } // max-heap
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int findKthSmallest(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < k; i++) {
            maxHeap.offer(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            if (nums[i] < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.offer(nums[i]);
            }
        }
        return maxHeap.peek();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun findKthSmallest(nums: IntArray, k: Int): Int {
        val maxHeap = PriorityQueue<Int>(Collections.reverseOrder())
        for (i in nums.indices) {
            maxHeap.add(nums[i])
            if (maxHeap.size > k) {
                maxHeap.poll()
            }
        }
        return maxHeap.peek() ?: -1
    }
}
1
2
3
4
5
6
7
8
9

import heapq

def find_kth_smallest(nums: list[int], k: int) -> int:
    max_heap = nums[:k]
    heapq._heapify_max(max_heap)
    for num in nums[k:]:
        if num < max_heap[0]:
            heapq._heapreplace_max(max_heap, num)
    return max_heap[0]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

use std::collections::BinaryHeap;

impl Solution {
    pub fn find_kth_smallest(nums: &mut Vec<i32>, k: i32) -> i32 {
        let mut max_heap = BinaryHeap::new();
        for &num in nums.iter().take(k as usize) {
            max_heap.push(num);
        }
        for &num in nums.iter().skip(k as usize) {
            if num < *max_heap.peek().unwrap() {
                max_heap.pop();
                max_heap.push(num);
            }
        }
        *max_heap.peek().unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    findKthSmallest(nums: number[], k: number): number {
        const maxHeap = new MaxPriorityQueue();
        for (let i = 0; i < nums.length; i++) {
            maxHeap.enqueue(nums[i]);
            if (maxHeap.size() > k) {
                maxHeap.dequeue();
            }
        }
        return maxHeap.front().element;
    }
}

Complexity

  • ⏰ Time complexity: O(n log k), because we process n elements and each heap operation takes O(log k).
  • 🧺 Space complexity: O(k), for storing the k elements in the heap.

Method 3 – Sorting

Intuition

Sorting the array puts all elements in order, so the kth smallest is at index k-1.

Approach

  1. Sort the array in ascending order.
  2. Return the element at index k-1.

Code

1
2
3
4
5
6
7

class Solution {
public:
    int findKthSmallest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[k - 1];
    }
};
1
2
3
4
5
6

import "sort"

func findKthSmallest(nums []int, k int) int {
    sort.Ints(nums)
    return nums[k-1]
}
1
2
3
4
5
6
7
8

import java.util.Arrays;

class Solution {
    public int findKthSmallest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[k - 1];
    }
}
1
2
3
4
5
6

class Solution {
    fun findKthSmallest(nums: IntArray, k: Int): Int {
        nums.sort()
        return nums[k - 1]
    }
}
1
2
3

def find_kth_smallest(nums: list[int], k: int) -> int:
    nums.sort()
    return nums[k - 1]
1
2
3
4
5
6

impl Solution {
    pub fn find_kth_smallest(nums: &mut Vec<i32>, k: i32) -> i32 {
        nums.sort();
        nums[(k - 1) as usize]
    }
}
1
2
3
4
5
6

class Solution {
    findKthSmallest(nums: number[], k: number): number {
        nums.sort((a, b) => a - b);
        return nums[k - 1];
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), due to the sorting step.
  • 🧺 Space complexity: O(1), if the sort is in-place, otherwise O(n).

Method 4 – Min Heap

Intuition

A min heap allows us to efficiently extract the smallest elements.

Approach

  1. Build a min heap from the array.
  2. Extract the minimum k times; the kth extraction is the kth smallest.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int findKthSmallest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> minHeap(nums.begin(), nums.end());
        int kthSmallest = 0;
        for (int i = 0; i < k; ++i) {
            kthSmallest = minHeap.top();
            minHeap.pop();
        }
        return kthSmallest;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import "container/heap"

func findKthSmallest(nums []int, k int) int {
    minHeap := &IntHeap{}
    heap.Init(minHeap)
    for _, num := range nums {
        heap.Push(minHeap, num)
    }
    var kthSmallest int
    for i := 0; i < k; i++ {
        kthSmallest = heap.Pop(minHeap).(int)
    }
    return kthSmallest
}

// IntHeap is a type that implements heap.Interface for a slice of integers.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } // min-heap
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.util.PriorityQueue;

class Solution {
    public int findKthSmallest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
        }
        int kthSmallest = 0;
        for (int i = 0; i < k; i++) {
            kthSmallest = minHeap.poll();
        }
        return kthSmallest;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun findKthSmallest(nums: IntArray, k: Int): Int {
        val minHeap = PriorityQueue<Int>()
        for (num in nums) {
            minHeap.add(num)
        }
        var kthSmallest = 0
        for (i in 0 until k) {
            kthSmallest = minHeap.poll() ?: 0
        }
        return kthSmallest
    }
}
1
2
3
4
5
6
7
8
9

import heapq

def find_kth_smallest(nums: list[int], k: int) -> int:
    min_heap = nums[:]
    heapq.heapify(min_heap)
    kth_smallest = 0
    for _ in range(k):
        kth_smallest = heapq.heappop(min_heap)
    return kth_smallest
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

use std::collections::BinaryHeap;

impl Solution {
    pub fn find_kth_smallest(nums: &mut Vec<i32>, k: i32) -> i32 {
        let mut min_heap = BinaryHeap::new();
        for &num in nums.iter() {
            min_heap.push(Reverse(num));
        }
        let mut kth_smallest = 0;
        for _ in 0..k {
            kth_smallest = min_heap.pop().unwrap().0;
        }
        kth_smallest
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    findKthSmallest(nums: number[], k: number): number {
        const minHeap = new MinPriorityQueue();
        for (let num of nums) {
            minHeap.enqueue(num);
        }
        let kthSmallest: number;
        for (let i = 0; i < k; i++) {
            kthSmallest = minHeap.dequeue().element;
        }
        return kthSmallest;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), for building the heap and extracting elements.
  • 🧺 Space complexity: O(n), for storing the elements in the heap.

Method 5 – Max Heap of Size K

Intuition

Maintain a max heap of size k to keep track of the k smallest elements seen so far.

Approach

  1. Build a max heap with the first k elements.
  2. For each remaining element, if it is smaller than the heap’s root, replace the root and heapify.
  3. The root of the heap is the kth smallest.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int findKthSmallest(vector<int>& nums, int k) {
        priority_queue<int> maxHeap(nums.begin(), nums.begin() + k);
        for (auto it = nums.begin() + k; it != nums.end(); ++it) {
            if (*it < maxHeap.top()) {
                maxHeap.pop();
                maxHeap.push(*it);
            }
        }
        return maxHeap.top();
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

import "container/heap"

func findKthSmallest(nums []int, k int) int {
    maxHeap := &IntHeap{}
    heap.Init(maxHeap)
    for i, num := range nums {
        if i < k {
            heap.Push(maxHeap, num)
        } else if num < (*maxHeap)[0] {
            heap.Pop(maxHeap)
            heap.Push(maxHeap, num)
        }
    }
    return (*maxHeap)[0]
}

// IntHeap is a type that implements heap.Interface for a slice of integers.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] } // max-heap
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import java.util.PriorityQueue;

class Solution {
    public int findKthSmallest(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < k; i++) {
            maxHeap.offer(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            if (nums[i] < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.offer(nums[i]);
            }
        }
        return maxHeap.peek();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun findKthSmallest(nums: IntArray, k: Int): Int {
        val maxHeap = PriorityQueue<Int>(k, Collections.reverseOrder())
        for (i in nums.indices) {
            if (i < k) {
                maxHeap.add(nums[i])
            } else if (nums[i] < maxHeap.peek()!!) {
                maxHeap.poll()
                maxHeap.add(nums[i])
            }
        }
        return maxHeap.peek()!!
    }
}
1
2
3
4
5
6
7
8
9

import heapq

def find_kth_smallest(nums: list[int], k: int) -> int:
    max_heap = [-x for x in nums[:k]]
    heapq.heapify(max_heap)
    for num in nums[k:]:
        if -num > max_heap[0]:
            heapq.heapreplace(max_heap, -num)
    return -max_heap[0]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

use std::collections::BinaryHeap;

impl Solution {
    pub fn find_kth_smallest(nums: &mut Vec<i32>, k: i32) -> i32 {
        let mut max_heap = BinaryHeap::new();
        for &num in nums.iter().take(k as usize) {
            max_heap.push(num);
        }
        for &num in nums.iter().skip(k as usize) {
            if num < *max_heap.peek().unwrap() {
                max_heap.pop();
                max_heap.push(num);
            }
        }
        *max_heap.peek().unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    findKthSmallest(nums: number[], k: number): number {
        const maxHeap = new MaxPriorityQueue({ priority: x => x });
        for (let i = 0; i < k; i++) {
            maxHeap.enqueue(nums[i]);
        }
        for (let i = k; i < nums.length; i++) {
            if (nums[i] < maxHeap.front().element) {
                maxHeap.dequeue();
                maxHeap.enqueue(nums[i]);
            }
        }
        return maxHeap.front().element;
    }
}

Complexity

  • ⏰ Time complexity: O(n log k), for processing n elements with heap operations.
  • 🧺 Space complexity: O(k), for the heap storage.

Method 6 – QuickSelect (Order Statistics)

Intuition

QuickSelect partitions the array so that the kth smallest is in its correct position, similar to quicksort but only recursing on one side.

Approach

  1. Partition the array around a pivot.
  2. If the pivot is at index k-1, return it.
  3. Otherwise, recurse on the appropriate side.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
public:
    int findKthSmallest(vector<int>& nums, int k) {
        return quickSelect(nums, 0, nums.size() - 1, k - 1);
    }

private:
    int quickSelect(vector<int>& nums, int left, int right, int k) {
        if (left == right) {
            return nums[left];
        }
        int pivotIndex = partition(nums, left, right);
        if (k == pivotIndex) {
            return nums[k];
        } else if (k < pivotIndex) {
            return quickSelect(nums, left, pivotIndex - 1, k);
        } else {
            return quickSelect(nums, pivotIndex + 1, right, k);
        }
    }

    int partition(vector<int>& nums, int left, int right) {
        int pivot = nums[right];
        int i = left;
        for (int j = left; j < right; ++j) {
            if (nums[j] <= pivot) {
                swap(nums[i], nums[j]);
                ++i;
            }
        }
        swap(nums[i], nums[right]);
        return i;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

func findKthSmallest(nums []int, k int) int {
    return quickSelect(nums, 0, len(nums)-1, k-1)
}

func quickSelect(nums []int, left, right, k int) int {
    if left == right {
        return nums[left]
    }
    pivotIndex := partition(nums, left, right)
    if k == pivotIndex {
        return nums[k]
    } else if k < pivotIndex {
        return quickSelect(nums, left, pivotIndex-1, k)
    } else {
        return quickSelect(nums, pivotIndex+1, right, k)
    }
}

func partition(nums []int, left, right int) int {
    pivot := nums[right]
    i := left
    for j := left; j < right; j++ {
        if nums[j] <= pivot {
            nums[i], nums[j] = nums[j], nums[i]
            i++
        }
    }
    nums[i], nums[right] = nums[right], nums[i]
    return i
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    public int findKthSmallest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, k - 1);
    }

    private int quickSelect(int[] nums, int left, int right, int k) {
        if (left == right) {
            return nums[left];
        }
        int pivotIndex = partition(nums, left, right);
        if (k == pivotIndex) {
            return nums[k];
        } else if (k < pivotIndex) {
            return quickSelect(nums, left, pivotIndex - 1, k);
        } else {
            return quickSelect(nums, pivotIndex + 1, right, k);
        }
    }

    private int partition(int[] nums, int left, int right) {
        int pivot = nums[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if (nums[j] <= pivot) {
                swap(nums, i, j);
                i++;
            }
        }
        swap(nums, i, right);
        return i;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    fun findKthSmallest(nums: IntArray, k: Int): Int {
        return quickSelect(nums, 0, nums.size - 1, k - 1)
    }

    private fun quickSelect(nums: IntArray, left: Int, right: Int, k: Int): Int {
        if (left == right) {
            return nums[left]
        }
        val pivotIndex = partition(nums, left, right)
        return when {
            k == pivotIndex -> nums[k]
            k < pivotIndex -> quickSelect(nums, left, pivotIndex - 1, k)
            else -> quickSelect(nums, pivotIndex + 1, right, k)
        }
    }

    private fun partition(nums: IntArray, left: Int, right: Int): Int {
        val pivot = nums[right]
        var i = left
        for (j in left until right) {
            if (nums[j] <= pivot) {
                nums[i] = nums[j].also { nums[j] = nums[i] }
                i++
            }
        }
        nums[i] = nums[right].also { nums[right] = nums[i] }
        return i
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import random

def find_kth_smallest(nums: list[int], k: int) -> int:
    def quickselect(left: int, right: int, k: int) -> int:
        if left == right:
            return nums[left]
        pivot_index = partition(left, right)
        if k == pivot_index:
            return nums[k]
        elif k < pivot_index:
            return quickselect(left, pivot_index - 1, k)
        else:
            return quickselect(pivot_index + 1, right, k)

    def partition(left: int, right: int) -> int:
        pivot = nums[right]
        i = left
        for j in range(left, right):
            if nums[j] <= pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[right] = nums[right], nums[i]
        return i

    return quickselect(0, len(nums) - 1, k - 1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

use rand::Rng;

impl Solution {
    pub fn find_kth_smallest(nums: &mut Vec<i32>, k: i32) -> i32 {
        let mut rng = rand::thread_rng();
        let n = nums.len();
        let mut left = 0;
        let mut right = n as i32 - 1;
        while left <= right {
            let pivot_index = (left + right) / 2;
            let pivot_new_index = partition(nums, left, right, pivot_index as usize);
            if pivot_new_index == k - 1 {
                return nums[pivot_new_index];
            } else if pivot_new_index < k - 1 {
                left = pivot_new_index as i32 + 1;
            } else {
                right = pivot_new_index as i32 - 1;
            }
        }
        -1
    }
}

fn partition(nums: &mut Vec<i32>, left: i32, right: i32, pivot_index: usize) -> usize {
    let pivot = nums[pivot_index];
    nums.swap(pivot_index, right as usize);
    let mut store_index = left;
    for i in left..right {
        if nums[i as usize] < pivot {
            nums.swap(i as usize, store_index as usize);
            store_index += 1;
        }
    }
    nums.swap(store_index as usize, right as usize);
    store_index as usize
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    findKthSmallest(nums: number[], k: number): number {
        const quickSelect = (left: number, right: number, k: number): number => {
            if (left === right) {
                return nums[left];
            }
            const pivotIndex = this.partition(nums, left, right);
            if (k === pivotIndex) {
                return nums[k];
            } else if (k < pivotIndex) {
                return quickSelect(left, pivotIndex - 1, k);
            } else {
                return quickSelect(pivotIndex + 1, right, k);
            }
        };

        return quickSelect(0, nums.length - 1, k - 1);
    }

    private partition(nums: number[], left: number, right: number): number {
        const pivot = nums[right];
        let i = left;
        for (let j = left; j < right; j++) {
            if (nums[j] <= pivot) {
                [nums[i], nums[j]] = [nums[j], nums[i]];
                i++;
            }
        }
        [nums[i], nums[right]] = [nums[right], nums[i]];
        return i;
    }
}

Complexity

  • ⏰ Time complexity: O(n) on average, O(n^2) in the worst case (depends on pivot choice).
  • 🧺 Space complexity: O(1) for iterative version, O(log n) for recursive stack space.

You can use any of these methods depending on the constraints and requirements of your problem.