K-th smallest element in unsorted array

Given an array v of distinct numbers, and a number k where k is smaller than the size of v, find the k-th smallest element in the array. A simple solution would be first sorting the array in growing order and than selecting the k-th element which can be done in θ(n logn). However, your program MUST run in θ(n) on average.

Difficulty: Medium.


There are two lines.

  • The first line contains an integer k
  • The second line contains an integer l such that k<=l and l is the length of the array v.
  • The second line consists of l numbers separated by space which represent the array v.

At the end of each line, there are no extra spaces, and there is a \n.


One line containing 1 integer, which is the k-th smallest number in v.





3 5 2 8 4




You can borrow the idea of Quicksort.

Solution: C++


using namespace std;

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;

int partition(int v[], int l, int r){
    // same as quicksort
    int p = v[r-1]; // pivot is the last element
    int j=l;
    for(int i=l;i<r-1;i++){
            swap(&v[i], &v[j]);
    swap(&v[j], &v[r-1]);
    return j;

void find_k_smallest(int v[], int k, int l, int r){
    //find the pivot such that v[0...p-1]<v[p]<v[p+1...l]
    int p = partition(v, l, r);
    //if the pivot is the k-th element, we are done since v[0...k-1]<v[k]<v[k+1...l]
    //the solution is in v[0...p-1]
        find_k_smallest(v, k, l, p);
    //the solution is in v[p+1...l]
    find_k_smallest(v, k, p+1, r);

int main(){
    int k;
    cin>>k; //index k of the k-th smallest number in the array
    int l;
    cin>>l; //length of the array
    int v[l];
    for(int i=0; i<l; i++)
    find_k_smallest(v, k, 0, l);


Related posts

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s