Kth smallest element in the array using constant space when array can 't be modified | C ++ implementation of the approach ; Function to return the kth smallest element from the array ; Minimum and maximum element from the array ; Modified binary search ; To store the count of elements from the array which are less than mid and the elements which are equal to mid ; If mid is the kth smallest ; If the required element is less than mid ; If the required element is greater than mid ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int kthSmallest ( int * arr , int k , int n ) { int low = * min_element ( arr , arr + n ) ; int high = * max_element ( arr , arr + n ) ; while ( low <= high ) { int mid = low + ( high - low ) / 2 ; int countless = 0 , countequal = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( arr [ i ] < mid ) ++ countless ; else if ( arr [ i ] == mid ) ++ countequal ; } if ( countless < k && ( countless + countequal ) >= k ) { return mid ; } else if ( countless >= k ) { high = mid - 1 ; } else if ( countless < k && countless + countequal < k ) { low = mid + 1 ; } } } int main ( ) { int arr [ ] = { 7 , 10 , 4 , 3 , 20 , 15 } ; int n = sizeof ( arr ) / sizeof ( int ) ; int k = 3 ; cout << kthSmallest ( arr , k , n ) ; return 0 ; }