@@ -11,4 +11,42 @@ class Solution {
1111
1212return heap.peek()
1313 }
14+
15+ // O(n) average time complexity - Quick Select algorithm
16+ fun findKthLargestRecursive (nums : IntArray ,k : Int ):Int = quickSelect(
17+ array= nums,
18+ startIndex= 0 ,
19+ endIndex= nums.lastIndex,
20+ k= k
21+ )
22+
23+ private fun quickSelect (
24+ array : IntArray ,
25+ startIndex : Int ,
26+ endIndex : Int ,
27+ k : Int ,
28+ ):Int {
29+ // find a valid position for pivot such that all values that
30+ // appear before the pivot are lower than the value of pivot,
31+ // and, all values that appear after the pivot are greater
32+ // than the pivot.
33+ @Suppress(" UnnecessaryVariable" val pivotIndex= endIndex
34+ var validIndexForPivot= startIndex
35+ for (iin startIndex until endIndex) {
36+ if (array[i]< array[pivotIndex]) {
37+ val temp= array[i]
38+ array[i]= array[validIndexForPivot]
39+ array[validIndexForPivot]= temp
40+ validIndexForPivot++
41+ }
42+ }
43+ // put pivot element in it's sorted position
44+ val temp= array[validIndexForPivot]
45+ array[validIndexForPivot]= array[pivotIndex]
46+ array[pivotIndex]= temp
47+
48+ return if (validIndexForPivot== (array.size- k)) array[validIndexForPivot]
49+ else if (validIndexForPivot> array.size- k) quickSelect(array, startIndex, validIndexForPivot- 1 , k)
50+ else quickSelect(array, validIndexForPivot+ 1 , endIndex, k)
51+ }
1452}