Kth Smallest Element

Medium
619.

Kth Smallest Element

Kth Smallest Element is a medium coding problem on arrays, sorting and quickselect, asked in Amazon, Microsoft and Flipkart interviews.

Given an array arr of distinct integers and a number k, return the k-th smallest element — the value that would sit at index k - 1 if the array were sorted ascending.

k is 1-based and always valid.

Example 1

Input
arr = [7,10,4,3,20,15], k = 3
Output
7
Explanation
Sorted it is [3,4,7,10,15,20]; the 3rd value is 7.

Example 2

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

Example 3

Input
arr = [5], k = 1
Output
5

Constraints

  • 1 <= arr.length <= 100000
  • 1 <= k <= arr.length
  • 1 <= arr[i] <= 1000000000
  • All values in arr are distinct.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(arr, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Kth Smallest Element — Solution in Python, Java & C++

Kth Smallest Element solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Kth Smallest Element is a medium coding problem on arrays, sorting and quickselect, asked in Amazon, Microsoft and Flipkart interviews.

Problem statement

Given an array arr of distinct integers and a number k, return the k-th smallest element — the value that would sit at index k - 1 if the array were sorted ascending.

k is 1-based and always valid.

Example 1

Input: arr = [7,10,4,3,20,15], k = 3
Output: 7
Explanation: Sorted it is [3,4,7,10,15,20]; the 3rd value is 7.

Example 2

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

Example 3

Input: arr = [5], k = 1
Output: 5

Constraints

  • 1 <= arr.length <= 100000
  • 1 <= k <= arr.length
  • 1 <= arr[i] <= 1000000000
  • All values in arr are distinct.

Hints for Kth Smallest Element

  1. Hint 1

    Sorting and indexing is O(n log n) and completely acceptable.

  2. Hint 2

    The interview answer is quickselect: partition like quicksort, but recurse into only the side that contains index k - 1.

  3. Hint 3

    A max-heap of size k is the third standard route and streams the input.

How to solve Kth Smallest Element

Sorting puts the answer at index k - 1 by definition. The faster route is quickselect: partition around a pivot and recurse into only the half that can hold the target index, which averages linear time.

Approach

  1. Sort a copy of arr ascending.
  2. Return the element at index k - 1.
  3. For quickselect instead: partition around a pivot at final index p. If p == k - 1 the pivot is the answer; if p > k - 1 recurse left, otherwise recurse right.

Why it works

After partitioning, the pivot is in its final sorted position, so comparing p with k - 1 tells you which side holds the answer — the other side can be discarded entirely. Halving the work each time gives O(n) expected total.

Complexity

  • Time — O(n log n) sorting, O(n) expected with quickselect
  • Space — O(n) for the copy, O(1) extra for in-place quickselect

Pitfalls

  • Off-by-one: k is 1-based but array indices are 0-based.
  • Quickselect degrades to O(n²) on adversarial pivots — randomise or use median-of-three.

Reference solution

Python

from typing import List

def kthSmallest(arr: List[int], k: int) -> int:
    return sorted(arr)[k - 1]

Java

public static int kthSmallest(int[] arr, int k) {
    int[] s = arr.clone();
    Arrays.sort(s);
    return s[k - 1];
}

C++

int kthSmallest(vector<int>& arr, int k) {
    vector<int> s = arr;
    nth_element(s.begin(), s.begin() + (k - 1), s.end());
    return s[k - 1];
}

JavaScript

var kthSmallest = function(arr, k) {
    var s = arr.slice().sort(function(a, b) { return a - b; });
    return s[k - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms