K’th smallest element in unordered list

You are given an unordered list of integers, you need to find the K’th smallest integer in that list.

Sample Input: Arr = { 7, 4, 6, 3, 9, 1 }, K = 2
Expected Output: 3
Explanation: The second smallest element in the array is 3.

Time complexity – Average -> O (N), where N is the size of the array.

Algorithm

The algorithm is similar to quicksort algorithm for sorting an array. The partition function is exactly similar to that of quicksort algorithm. After finding the pivot element, instead of recurring for both the sides of the pivot element, we recur only for that part of the array which contains the K’th smallest element. If index of partitioned element, is smaller than K, we recur for right part of the array and if it is greater than K, we recur for left part. If the partitioned index is equal to K, we return the element. Thus, the time complexity becomes O (N) instead of the average case time complexity of QuickSort which is O (Nlog(N)). Note, that the worst case time complexity is till O (N*N).

#include <bits/stdc++.h>
using namespace std;

int partition(vector<int> &arr, int l, int r){
	int pivot = arr[r];
	int i = l;
	for(int j=l; j<r; j++){
		if(arr[j]<=pivot){
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;

			i++;
		}
	}
	int temp = arr[i];
	arr[i] = arr[r];
	arr[r] = temp;
	return i;
}

int quickSelect(vector<int> &arr, int low, int high, int k){
	if(k>0 && k < high - low + 1){
		int pivot = partition(arr, low, high);
		if(pivot - low == k-1){
			return arr[pivot];
		}
		if(pivot - low > k-1){
			return quickSelect(arr, low, pivot-1, k);
		}
		return quickSelect(arr, pivot+1, high, k-pivot+low-1);
	}
	return INT_MAX;
}

int main(){
	vector<int> arr{ 7, 4, 6, 3, 9, 1 };
	int k = 2;
	cout<<quickSelect(arr, 0, arr.size()-1, k);
	return 0;
}

Also, take a look at another popular interview problem Permutations of a string using Backtracking.

One comment

Leave a Reply

Your email address will not be published.