Kth smallest element in an unsorted array

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
25 upvotes
Asked in companies
DelhiveryAmazonGrab

Problem statement

Given an unsorted array ‘arr’ of distinct integers and an integer ‘k’, your task is to find the ‘k-th’ smallest element in the array.

Example: 
n = 5, k = 2 and arr[] = {6, 5, 4, 8, 7}
The array elements in sorted order are [4, 5, 6, 7, 8]. The ‘2-nd’ smallest element in the array is 5, so the answer is 5.
Note: 
1. Don’t print anything. Return the value of ‘k-th’ smallest element.
2. ‘k’ is a positive integer and not greater than the size of the array.
3. The array ‘arr’ is unsorted, and all the elements of the array are distinct.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘n’ and ‘k’, where ‘n’ is the array’s size.

The second line of each test case contains ‘n’ space-separated integers denoting the array elements.
Output format: 
For each test case, return the ‘k-th’ smallest element in the array.

Output for each query is printed in a separate line.
Constraints: 
1 <= T <= 10
1 <= n <= 1000
1 <= k <= n
-10^6 <= arr[i] <=10^6

Where ‘T’ is the total number of test cases, ‘n’ denotes the array’s size, ‘k’ denotes the ‘k-th’ smallest element that you must return, and ‘arr[i]’ denotes the range of elements in the array.

Time limit: 1 second

Sample input 1:

2
5 3
1 2 3 4 5
5 4
1 3 2 6 5

Sample output 1:

3
5

Explanation of sample input 1:

Test Case 1:
The array elements in sorted order are [1, 2, 3, 4, 5]. The ‘3-rd’ smallest element in the array is 3, so the answer is 3.

Test Case 2:
The array elements in sorted order are [1, 2, 3, 5, 6]. The ‘4-th’ smallest element in the array is 5, so the answer is 5.

Sample input 2:

2
5 1
10 23 45 8 21
6 6
20 10 30 40 60 50

Sample output 2:

8
60
Hint

Can we use sorting to solve this problem?

Approaches (3)
Sorting the array

If we sort the given array in ascending order, then the required answer would be the element at index ‘k’ in the sorted array.

  • Sort the given array in ascending order.
  • The ‘k-th’ element (at index ‘k-1’) in the array will be the ‘k-th’ smallest element, return it as the final answer.
Time Complexity

O(n*log(n)), where ‘n’ is the array’s size. 

 

Sorting algorithms like Merge Sort, STL sort(), etc. require ‘O(n*log(n))’ time, and we can access the ‘k-th’ element in ‘O(1)’.

Space Complexity

O(n), where ‘n’ is the array’s size.

 

To store ‘n’ elements in an array, we require ‘O(n)’ space, and in-place sorting algorithms need ‘O(1)’ space.

Code Solution
(100% EXP penalty)
Kth smallest element in an unsorted array
Full screen
Console