Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 1 Feb, 2021

Kth Smallest and Largest Element of Array

Easy
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.
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

Approaches

01 Approach

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’