Find the Kth Largest Integer in the Array

Tagged: Array, String, Divide and Conquer, Sorting, Priority Queue, Heap, Quickselect

Problem

Given an array of strings where each element represents an integer, our task is to find the K^th Largest Integer in the Array. The K^th largest integer here is in the sorted order, not in the K^th 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

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

Kotlin
Java

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

Kotlin
Java

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

Kotlin
Java

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;
}

Find the Kth Largest Integer in the Array

Problem#

Solution#

Sorting#

Priority Queue (Heap) - Two Pass#

Priority Queue (Heap) - One Pass#

Quickselect#