$$ \newcommand\Tr{\mathrm{Tr}} \newcommand{\braket}[2]{\langle #1 \mid #2 \rangle} \newcommand\I{\mathbb{I}} \newcommand{\avg}[1]{\left< #1 \right>} \newcommand{\RD}{D} \newcommand{\ri}{\mathrm{i}} \DeclareMathOperator{\sign}{sign} \DeclareMathOperator{\Sign}{Sign} \newcommand{\ii}{\mathrm i} \newcommand{\vv}{\mathrm v} \newcommand{\ff}{\mathrm f} \newcommand{\mm}{\mathrm m} \newcommand{\ee}{\mathrm e} \newcommand{\xx}{\mathrm x} \newcommand{\RR}{\mathrm R} \newcommand{\dd}{\mathrm d} \newcommand{\FF}{\mathrm F} \newcommand{\BB}{\mathrm B} \newcommand{\vph}{v_{\mathrm{ph}}} $$

Find the Kth Largest Integer in the Array

Problem

Given an array of strings where each element represents an integer, our task is to find the Kth Largest Integer in the Array. The Kth largest integer here is in the sorted order, not in the Kth distinct element.
For example,

Input: nums = ["3","6","7","10"], k = 4
Output: "3"
Explanation: 3 is the fourth largest element in the sorted order ["3","6","7","10"].
Input: nums = ["2","21","12","1"], k = 3
Output: "2"
Explanation: 2 is the third largest element in the sorted order ["1","2","12","21"].
Input: nums = ["0","0"], k = 2
Output: "0"
Explanation: 0 is the second largest element in the sorted order ["0","0"].

Solution

Sorting

fun kthLargestNumber(nums: Array<String>, k: Int): String {
    nums.sortWith(
        compareBy<String> { it.length }
            .thenBy { it }
    )
    return nums[nums.size - k]       
}

public String kthLargestNumber(String[] nums, int k) {
    Arrays.sort(nums, Comparator.comparing(String::length).thenComparing(it -> it));
    return nums[nums.length - k];    
}

Priority Queue (Heap) - Two Pass

fun kthLargestNumber(nums: Array<String>, k: Int): String {
    val priorityQueue = PriorityQueue(
        compareByDescending<String> { it.length }
            .thenByDescending { it }
    )
    nums.forEach {
        priorityQueue.add(it)
    }

    var count = 1
    while (priorityQueue.isNotEmpty()) {
        val num = priorityQueue.poll()
        if (count == k)
            return num

        count++
    }

    return "0"      
}

public String kthLargestNumber(String[] nums, int k) {
    PriorityQueue<String> priorityQueue = new PriorityQueue(
            Comparator.comparing(String::length).reversed().thenComparing(Comparator.reverseOrder())
    );

    for (String num : nums) {
        priorityQueue.add(num);
    }

    int count = 1;
    while (!priorityQueue.isEmpty()) {
        String num = priorityQueue.poll();
        if (count == k)
            return num;

        count++;
    }

    return "0";   
}

Priority Queue (Heap) - One Pass

fun kthLargestNumber(nums: Array<String>, k: Int): String {
    val priorityQueue = PriorityQueue(
        compareBy<String> { it.length }
            .thenBy { it }
    )
    nums.forEach {
        if (priorityQueue.size < k)
            priorityQueue.add(it)
        else {
            if (priorityQueue.peek().length < it.length ||
                (priorityQueue.peek().length == it.length && priorityQueue.peek() < it)
            ) {
                priorityQueue.remove()
                priorityQueue.add(it)
            }
        }
    }

    return priorityQueue.peek()   
}

public String kthLargestNumber(String[] nums, int k) {
    PriorityQueue<String> priorityQueue = new PriorityQueue(
            Comparator.comparing(String::length).thenComparing(it -> it)
    );

    for (String num : nums) {
        if (priorityQueue.size() < k)
            priorityQueue.add(num);
        else {
            if (priorityQueue.peek().length() < num.length() || 
                    (priorityQueue.peek().length() == num.length() && priorityQueue.peek().compareTo(num) < 0)) {
                priorityQueue.remove();
                priorityQueue.add(num);
            }
        }
    }

    return priorityQueue.peek();
}

Quickselect

fun kthLargestNumber(nums: Array<String>, k: Int): String {
    return quickSelect(nums, nums.size - k, 0, nums.size - 1)  
}

private fun quickSelect(nums: Array<String>, k: Int, low: Int, high: Int): String {
    if (low == high) return nums[low]

    val position: Int = hoarePartition(nums, low, high)
    return if (k <= position) quickSelect(nums, k, low, position) else quickSelect(nums, k, position + 1, high)
}

private fun hoarePartition(nums: Array<String>, low: Int, high: Int): Int {
    val pivot = nums[(low + high) / 2]

    var i = low - 1
    var j = high + 1
    while (true) {
        do {
            i++
        } while (nums[i].length < pivot.length
            || nums[i].length == pivot.length && nums[i] < pivot
        )
        do {
            j--
        } while (nums[j].length > pivot.length
            || nums[j].length == pivot.length && nums[j] > pivot
        )
        if (i >= j) return j
        nums[i] = nums[j].also {
            nums[j] = nums[i]
        }
    }
}

public String kthLargestNumber(String[] nums, int k) {
    return quickSelect(nums, nums.length - k, 0, nums.length - 1);
}

private String quickSelect(String[] nums, int k, int low, int high) {
    if (low == high)
        return nums[low];

    int position = hoarePartition(nums, low, high);
    if (k <= position)
        return quickSelect(nums, k, low, position);
    else
        return quickSelect(nums, k, position + 1, high);
}

private int hoarePartition(String[] nums, int low, int high) {
    String pivot = nums[(low + high) / 2];

    int i = low - 1;
    int j = high + 1;
    while (true) {
        do {
            i++;
        } while (nums[i].length() < pivot.length()
                || (nums[i].length() == pivot.length() && nums[i].compareTo(pivot) < 0));

        do {
            j--;
        } while (nums[j].length() > pivot.length()
                || (nums[j].length() == pivot.length() && nums[j].compareTo(pivot) > 0));

        if (i >= j)
            return j;

        swap(nums, i, j);
    }
}

private void swap(String[] nums, int a, int b) {
    String temp = nums[b];
    nums[b] = nums[a];
    nums[a] = temp;
}