Kth Smallest and Largest Element of Array

Easy
0/40
Average time to solve is 15m
profile
Contributed by
275 upvotes
Asked in companies
HSBCSalesforceTech Mahindra

Problem statement

You are given an array ‘Arr’ consisting of ‘N’ distinct integers and a positive integer ‘K’. Find out Kth smallest and Kth largest element of the array. It is guaranteed that K is not greater than the size of the array.

Example:

Let ‘N’ = 4,  ‘Arr’ be [1, 2, 5, 4] and ‘K’ = 3.  
then the elements of this array in ascending order is [1, 2, 4, 5].  Clearly, the 3rd smallest and largest element of this array is 4 and 2 respectively.
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 next 2*T lines represent the ‘T’ test cases.

The first line of each test case contains two space-separated integers  ‘N’ and ‘K’ respectively.

The second line of the test case contains ‘N’ space-separated integers representing elements of the array ‘Arr’.
Output format :
For each test case, print a line consisting of two space-separated integers that represent the Kth smallest and Kth largest elements of the array.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function. In the given function, you need to return an array consisting of 2 integers, where the first integer gives Kth smallest element and the second integer gives the Kth largest element.
Constraints:
1 <= T <= 50
1 <= N <= 10^4
1 <= K <= N
-10^9 <= Arr[i] <= 10^9

Where ‘T’ is the total number of test cases, ‘N’ is the size of array ‘Arr’ and Arr[i] is the element of the given array.

Time limit: 1 sec
Sample Input 1:
2
4 4
5 6 7 2
4 3
1 2 5 4
Sample Output 1:
7 2 
4 2
Explanation of Sample Input 1:
Test case 1:
Here, ‘N’ = 4, ‘Arr’ = [5, 6, 7, 2] and ‘K’ = 3.
Elements of the array in ascending order are [2, 5, 6, 7]
Thus the 4rd smallest and 4rd largest elements of this array are 7 and 2 respectively.

Test case 2:
See problem statement for an explanation.
Sample Input 2:
 2
 1 1
 2
 5 1
 5 4 3 2 1
Sample Output 2:
 2 2
 1 5
Hint

Repeatedly find the smallest element of the array and replace it with an infinite value.

Approaches (4)
Brute Force (TLE)

Observe that the Kth largest element of the array is (N - K + 1)th smallest element of the array.  We iterate over the given array, find the smallest element of the array and replace it with an infinite value, and then again we find the smallest array and replace it with an infinite value. We repeat this process max(K, N-K+1) times. The smallest element we obtained at Kth step is Kth smallest element of the array and the smallest element we obtained at (N-K+1)th step is the Kth largest element of the array.

 

Algorithm

  • Create two integer variables ‘kSmall’ and  ‘kLarge’. ‘kSmall’ will give the Kth smallest element of the array and ‘kLarge’ will give the Kth largest element of the array.
  • Run a loop where ‘i’ ranges from 1 to max(K, N-K+1) and for each ‘i’ do the following.
    • Iterate over the array and find the index of the smallest element.
    • If the value of ‘i’ is K then assign this smallest element to ‘kSmall’.
    • If the value of ‘i’ is N-K+1 then assign this smallest element to ‘kLarge’.
    • Replace this smallest integer by an infinite value.
  • Create an array ‘result’ of size 2. Assign result[0] := ‘kSmall’ and result[1] := ‘kLarge’.
  • Return ‘result’
Time Complexity

O(N^2), where  ‘N’ is the size of the given array.

 

In the worst case (K=1 or K=N), we have to iterate the array N times to find the smallest integer, and finding the smallest integer takes O(N) time. Thus, the overall complexity will be O(N*N) = O(N^2).

Space Complexity

O(1)

 

Constant extra space is used here.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Kth Smallest and Largest Element of Array
Full screen
Console