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 i...read more

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

O(1)

Sorting algorithm like heap sort uses constant space.

O(N * logN), where  ‘N’ is the size of the given array.

Sorting takes O(NlogN) time.

/*
    Time complexity: O(NlogN)
    Space complexity: O(1)

    Where  'N' is the size of the given array.
*/

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
	public static ArrayList kthSmallLarge(ArrayList arr, int n, int k) {

		// Sort the given array.
		Collections.sort(arr);

		ArrayList result = new ArrayList();
		result.add(arr.get(k - 1));
		result.add(arr.get(n - k));

		return result;
	}
}

/*
    Time complexity: O(NlogN)
    Space complexity: O(1)

    Where  ‘N’ is the size of the given array.
*/
#include 

vector kthSmallLarge(vector &arr, int n, int k)
{
    // Sort the given array.
    sort(arr.begin(), arr.end());

    // Kth Smallest and Kth Largest element of the array.
    vector result = {arr[k-1], arr[n-k]};

    return result;
}

'''
    Time complexity: O(N * logN)
    Space complexity: O(1)

    Where  ‘N’ is the size of the given array.
'''


def kthSmallLarge(arr, n, k):
    # Sort the given array.
    arr.sort()

    # Kth Smallest and Kth Largest element of the array.
    result = [arr[k-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...read more

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’

O(1)

Quickselect algorithm uses constant space.

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

Quickselect can be implemented in O(N) time if we always choose median as a pivot. The median divides array elements in two equal halves after partition,  and in the next recursive call we consider only one half. Since partition takes linear time, So for an array of size N quickselect should take time of order.

N + N/2 + N/4 + N/8 …. = O(N)

If we randomly select pivot then the worst case occurs when after partitioning ‘pivotIndex’ is always the last index of range. In that case com

/*
    Time complexity: O(N)
    Space complexity: O(1)

    Where 'N' is the size of the given array.
*/

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
	private static int partition(ArrayList arr, int left, int right, int pivotIndex) {
		int pivotValue = arr.get(pivotIndex);

		// Bring pivot element at the end of range.
		Collections.swap(arr, pivotIndex, right);

		int current = left;

		for (int i = left; i < right; i++) {
			if (arr.get(i).intValue() < pivotValue) {

				Collections.swap(arr, current, i);
				current++;
			}
		}

		Collections.swap(arr, right, current);

		return current;
	}

	private static int quickSelect(ArrayList arr, int left, int right, int k) {
		if (left == right) {
			// Size of array is 1.
			return arr.get(left);
		}

		// Note we can select Median as pivot to guaranteed O(N) complexity always.
		int pivotIndex = left + (int)Math.random() % (right - left + 1);

		int partitionIndex = partition(arr, left, right, pivotIndex);

		if (partitionIndex >= k) {
			// Recur for right subarray
			return quickSelect(arr, left, partitionIndex - 1, k);
		}

		if (partitionIndex < k - 1) {
			// Recur for left subarray.
			return quickSelect(arr, partitionIndex + 1, right, k);
		}

		return arr.get(partitionIndex);
	}

	public static ArrayList kthSmallLarge(ArrayList arr, int n, int k) {
		ArrayList result = new ArrayList();

		// Kth smallest element
		result.add(quickSelect(arr, 0, n - 1, k));

		// Kth largest element
		result.add(quickSelect(arr, 0, n - 1, n - k + 1));

		return result;
	}
}

'''
    Time complexity: O(N)
    Space complexity: O(1)

    Where ‘N’ is the size of the given array and K is given integer.
'''

import random

def partition(arr, left, right, pivotIndex):
    pivotValue = arr[pivotIndex]

    # Bring pivot element at the end of range.
    get = arr[pivotIndex], arr[right]
    arr[right], arr[pivotIndex] = get

    current = left

    for i in range(left, right):
        if (arr[i] < pivotValue):
            get = arr[current], arr[i]
            arr[i], arr[current] = get
            current += 1

    get = arr[right], arr[current]
    arr[current], arr[right] = get

    return current


def quickSelect(arr, left, right, k):
    if (left == right):
        # Size of array is 1.
        return arr[left]

    # Note we can select Median as pivot to guaranteed O(N) complexity always.
    pivotIndex = left + int(random.random()) % (right-left+1)

    partitionIndex = partition(arr, left, right, pivotIndex)

    if (partitionIndex >= k):
        # Recur for right subarray
        return quickSelect(arr, left, partitionIndex-1, k)

    if (partitionIndex < (k-1)):
        # Recur for left subarray.
        return quickSelect(arr, partitionIndex+1, right, k)

    return arr[partitionIndex]


def kthSmallLarge(arr, n, k):
    result = [0, 0]
    # Kth smallest element
    result[0] = quickSelect(arr, 0, n-1, k)

    # Kth largest element
    result[1] = quickSelect(arr, 0, n-1, n-k+1)

    return result

/*
    Time complexity: O(N)
    Space complexity: O(1)

    Where ‘N’ is the size of the given array.
*/

int partition(vector &arr, int left, int right, int pivotIndex) 
{
    int pivotValue = arr[pivotIndex];
    
    // Bring pivot element at the end of range.
    swap(arr[pivotIndex], arr[right]); 

    int current = left;
    
    for(int i = left; i < right; i++) 
    {
        if(arr[i] < pivotValue) 
        {
            swap(arr[current], arr[i]);
            current++;
        }
    }
    swap(arr[right], arr[current]);
    
    return current;
}

int quickSelect(vector &arr, int left, int right, int k) 
{
    if(left == right)
    {
        // Size of array is 1.
        return arr[left];
    }
    
    // Note we can select Median as pivot to guaranteed O(N) complexity always.
    int pivotIndex = left + rand() % (right-left+1);
    
    int partitionIndex = partition(arr, left, right, pivotIndex);

    if(partitionIndex >= k)
    {
        // Recur for right subarray
        return quickSelect(arr, left, partitionIndex-1, k);
    }
    
    if(partitionIndex < k-1)
    {
        // Recur for left subarray.
        return quickSelect(arr, partitionIndex+1, right, k);
    }

    return arr[partitionIndex];
}

vector kthSmallLarge(vector &arr, int n, int k)
{
    vector result(2);
    
    // Kth smallest element
    result[0] = quickSelect(arr, 0, n-1, k);
    
    // Kth largest element
    result[1] = quickSelect(arr, 0, n-1, n-k+1);

    return result;
}