# 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 {
}

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) {
}

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)
else {
if (priorityQueue.peek().length < it.length ||
(priorityQueue.peek().length == it.length && priorityQueue.peek() < it)
) {
priorityQueue.remove()
}
}
}

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)
else {
if (priorityQueue.peek().length() < num.length() ||
(priorityQueue.peek().length() == num.length() && priorityQueue.peek().compareTo(num) < 0)) {
priorityQueue.remove();
}
}
}

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