Kth Smallest and Largest Element of Array

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’

Sort the given array in ascending order, the Kth smallest element will be at K-1 index and the Kth largest element of the array will be at  N - K index. 

Algorithm

• Sort the given array ‘Arr’ in ascending order using any O(nlogn) time and O(1) space algorithm, e.g HeapSort.
• Create an array ‘result’ of size 2. Assign result[0] := ‘Arr[K-1]’ and result[1] := Arr[N-K].
• Return ‘result’.

First, we create a min-heap of size ‘N’ from the given array ‘Arr’, Then we pop the first 

K-1’ elements from the top. Elements residing at the top/root of the min-heap is Kth smallest integer. Similarly, we create a max-heap of size ‘N’ from the given array ‘Arr’ and then pop the first ‘K-1’ element from the top of max-heap. Element residing at top/root of max-heap is Kth largest element.

Algorithm

• Create an array ‘result’ of size 2.
• Build Min-Heap from the given array.
• Pop from Min-Heap exactly K-1 times
• Assign the top element of Min-Heap to result[0].
• Build Max-Heap from the given array.
• Pop from Max-Heap exactly K-1 times
• Assign the top element of Max-Heap to result[1].
• Return ‘result’

Quickselect is a selection algorithm to find the Kth smallest element in an unordered list. It is related to the Quicksort sorting algorithm.  Like Quicksort, In Quickselect we also have a sub-procedure called a partition. In partition algorithm, we select some index as the pivot and in linear time we rearrange the list in such a way, that element at pivot reach to the index where it should be if this list is sorted in ascending order, and all the elements smaller than it should be on its left side and element greater than it should be on its right side.

Here is an algorithm that performs a partition in a given array ‘Arr’ about the element Arr[pivotIndex] and in the range between ‘left’ and ‘right’

• Initialize a variable ‘pivotValue’ := Arr[pivotIndex].
• Swap Arr[pivotIndex] with Arr[right].
• Initialize a variable ‘current’: = left.
• Run a loop where ‘i’ ranges from left to right-1 and in each iteration do the following.
  • If Arr[i] < ‘pivotValue’ then swap ‘Arr[current]’ with ‘Arr[i]’ and increment ‘current’ by 1.
• Swap Arr[right] with Arr[current].
• Return current.

In quicksort, we recursively sort both branches (i.e left and right side of index return by partition), leading to best-case O(n log n) time. However, when doing the selection, we already know which partition our desired element lies in, since the pivot is in its final sorted position, with all those preceding it in an unsorted order and all those following it in an unsorted order. Therefore, a single recursive call locates the desired element in the correct partition, and we build upon this for quickselect. 

The recursive algorithm for Quickselect using sub-procedure partition is as follows.

• Let define a function quickselect(Arr, left, right, K) where left and right is the leftmost and rightmost index of the window that can have Kth smallest element in the array ‘Arr’.
• If left == right  return Arr[left].
• Select a ‘pivotIndex’ between ‘left’ and ‘right’. In order to ensure the linear time complexity of Quickselect, we should choose ‘pivotIndex’ that has a median element of the array, This can be done by using the Median of medians algorithm.  For simplicity here we randomly select pivotIndex.
• Call sub-procedure partition and assign value return by it to the variable ‘partitionIndex’
• If ‘partitionIndex’ is greater than or equal to ‘K’  then recursively call this function by assigning ‘right’:= ‘partitionIndex’-1.
• If ‘partitionIndex’ is smaller than ‘K-1’  then recursively call this function by assigning ‘left’:= ‘partitionIndex’+1.
• Otherwise return Arr[pivotIndex].

This problem can be solved using Quickselect as follow -:

Algorithm

• Create an array ‘result’ of size 2.
• Find the Kth smallest element of the array ‘Arr’ using Quickselect and assign it to result[0].
• Find the (N-K+1)th smallest element of the array ‘Arr’ using Quickselect and assign it to result[1].
• Return ‘result’