findKthLargest.kt

class Solution {
    fun findKthLargest(nums: IntArray, k: Int): Int {
        return findKthSmallestInPlace(nums.toList(), nums.indices, nums.size - k)!!
    }

    fun findKthSmallestInPlace(nums: MutableList<Int>, range: IntRange, i: Int): Int? {
        if (nums.isEmpty()) return null
        if (nums.size == 1) return nums.first()

        if (range.toList().isEmpty()) return null
        if (range.toList().size == 1) return nums[range.first]
        if (i !in range.toList().indices) return null
        if (nums.subList(range).isAllSame) return nums[range.first]

        val mid = nums.partitionInPlace(range)
        val left = range.first until mid
        val right = mid..range.last
        // if (mid == i) return nums[mid] // follow-up optimization: for the i-th
        if (i < left.toList().size) {
            return findKthSmallestInPlace(nums, left, i) ?: findKthSmallestInPlace(nums, range, i)
        } else {
            return findKthSmallestInPlace(nums, right, i - left.toList().size) ?: findKthSmallestInPlace(nums, range, i)
        }
    }
}

val <T> List<T>.randomIndex: Int get() = kotlin.random.Random.nextInt(size)

val IntRange.random: Int get() = kotlin.random.Random.nextInt(first, last + 1)

val <T> List<T>.isAllSame: Boolean get() = if (isNotEmpty()) all { it == first() } else true

/**
 * returns mid
 */
fun <T: Comparable<T>> MutableList<T>.partitionInPlace(intRange: IntRange? = null): Int {
    val range = intRange ?: indices
    if (range.isEmpty()) return range.last
    if (range.toList().size == 2) {
        if (this[range.first] > this[range.last]) {
            swap(range.first, range.last)
        }
        return range.last
    }
    val pivot = range.random
    val pivotValue = this[pivot]
    swap(range.last, pivot)
    var lo = range.first
    var hi = range.last - 1

    while (lo <= hi) {
        if (this[lo] < pivotValue) {
            lo++
        } else {
            swap(lo, hi)
            hi--
        }
    }
    // swap(range.last, lo)
    return lo
}

fun <T> MutableList<T>.swap(i: Int, j: Int) {
    val tmp = this[i]
    this[i] = this[j]
    this[j] = tmp
}

fun <T> List<T>.subList(range: IntRange) = subList(range.first, range.last + 1)