# Find the Kth Largest Integer in the Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-kth-largest-integer-in-the-array)
Canonical: https://scaleengineer.com/dsa/problems/find-the-kth-largest-integer-in-the-array
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer), [Sorting](https://scaleengineer.com/algorithms/sorting), [Quickselect](https://scaleengineer.com/algorithms/quickselect)
**Data structures:** Array, String, Heap (Priority Queue)
---
## Problem
You are given an array of strings `nums` and an integer `k`. Each string in `nums` represents an integer without leading zeros.

Return _the string that represents the_ `kth` _**largest integer** in_ `nums`.

**Note**: Duplicate numbers should be counted distinctly. For example, if `nums` is `["1","2","2"]`, `"2"` is the first largest integer, `"2"` is the second-largest integer, and `"1"` is the third-largest integer.

**Example 1:**

**Input:** nums = ["3","6","7","10"], k = 4
**Output:** "3"
**Explanation:**
The numbers in nums sorted in non-decreasing order are ["3","6","7","10"].
The 4th largest integer in nums is "3".

**Example 2:**

**Input:** nums = ["2","21","12","1"], k = 3
**Output:** "2"
**Explanation:**
The numbers in nums sorted in non-decreasing order are ["1","2","12","21"].
The 3rd largest integer in nums is "2".

**Example 3:**

**Input:** nums = ["0","0"], k = 2
**Output:** "0"
**Explanation:**
The numbers in nums sorted in non-decreasing order are ["0","0"].
The 2nd largest integer in nums is "0".

**Constraints:**

* `1 <= k <= nums.length <= 104`
* `1 <= nums[i].length <= 100`
* `nums[i]` consists of only digits.
* `nums[i]` will not have any leading zeros.

# Approaches
## Full Sort
The most straightforward approach is to sort the entire array of number strings based on their numerical value. Once the array is sorted, the k-th largest element can be found at a specific index.
**Time:** O(N * log N * L). Here, N is the number of elements in the array, and L is the maximum length of a string. The sorting algorithm performs O(N * log N) comparisons, and each string comparison can take up to O(L) time. · **Space:** O(log N) to O(N). This is the auxiliary space required by the sorting algorithm. For example, Java's `Arrays.sort` for objects uses TimSort, which requires O(log N) space on average and O(N) in the worst case.
**Pros:** Simple to understand and implement, especially with built-in sorting functions.; The logic is clear and less prone to implementation errors.
**Cons:** It is inefficient because it sorts the entire array, even though we only need to find a single element.; The time complexity is worse than more specialized selection algorithms.
### Explanation
This method relies on a custom comparison logic since a simple lexicographical sort would incorrectly order numbers (e.g., "10" < "2"). The correct way to compare two number strings, `a` and `b`, is to first check their lengths. If `a.length()` is not equal to `b.length()`, the one with the greater length represents the larger number. If their lengths are equal, a standard lexicographical comparison will correctly determine their numerical order.

We can implement this logic in a custom `Comparator` and pass it to a built-in sort function. After sorting the array `nums` in non-decreasing order, the largest element is at the last index (`n-1`), the second largest is at `n-2`, and so on. Therefore, the k-th largest element is located at index `n - k`.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public String kthLargestNumber(String[] nums, int k) {
        // Custom comparator for numerical string comparison
        Comparator<String> numComparator = (a, b) -> {
            if (a.length() != b.length()) {
                return a.length() - b.length();
            }
            return a.compareTo(b);
        };

        // Sort the array using the custom comparator
        Arrays.sort(nums, numComparator);

        // The k-th largest element is at index n-k in the sorted array
        return nums[nums.length - k];
    }
}
```
### Algorithm
- Define a custom comparator to compare two number strings. The comparison logic is as follows:
  - If the lengths of the strings are different, the longer string is larger.
  - If the lengths are the same, use lexicographical comparison.
- Use a standard library sort function (e.g., `Arrays.sort` in Java) to sort the entire `nums` array in ascending order using the custom comparator.
- The k-th largest element will be at index `n - k`, where `n` is the length of the array. Return `nums[n - k]`.

## Min-Heap (Priority Queue)
A more optimized approach uses a min-heap (often implemented as a `PriorityQueue`) to efficiently track the `k` largest elements seen so far without needing to sort the entire array.
**Time:** O(N * log k * L). We iterate through `N` elements. For each element, we perform a heap operation (offer/poll) which takes O(log k) time. Each comparison within the heap takes O(L) time. · **Space:** O(k * L). The min-heap stores at most `k` elements, and each element is a string of up to length `L`.
**Pros:** More efficient than full sorting, especially when `k` is much smaller than `N`.; Processes the array in a single pass.
**Cons:** The space complexity is dependent on `k`, which can be large.; For small `k`, it's very efficient, but as `k` approaches `N`, its performance becomes similar to sorting.
### Explanation
This method avoids the O(N log N) complexity of a full sort by maintaining a data structure of a fixed size `k`. We use a min-heap, which always keeps the smallest of its elements at the top (root), ready for quick access.

The process involves iterating through the input array. For each number string, we add it to the min-heap. To ensure the heap's size never exceeds `k`, we check its size after each addition. If it's larger than `k`, we remove the smallest element, which is at the root. This ensures that the heap always holds the `k` largest numbers encountered up to that point.

After processing all `N` numbers, the min-heap contains the top `k` largest numbers from the entire array. The smallest among them is the k-th largest, which is conveniently located at the root of the min-heap.

```java
import java.util.PriorityQueue;
import java.util.Comparator;

class Solution {
    public String kthLargestNumber(String[] nums, int k) {
        // A min-heap that will store the k largest numbers.
        // The comparator ensures that smaller numbers have higher priority.
        PriorityQueue<String> minHeap = new PriorityQueue<>((a, b) -> {
            if (a.length() != b.length()) {
                return a.length() - b.length();
            }
            return a.compareTo(b);
        });

        for (String num : nums) {
            minHeap.offer(num);
            // If the heap size exceeds k, remove the smallest element.
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        // The root of the heap is the k-th largest element.
        return minHeap.peek();
    }
}
```
### Algorithm
- Create a min-priority queue (min-heap) with a capacity of `k`.
- The priority queue must use a custom comparator that orders strings based on their numerical value (same as the sorting approach).
- Iterate through each string `num` in the input array `nums`:
  - Add `num` to the min-heap.
  - If the heap's size exceeds `k`, remove the smallest element (the root of the min-heap).
- After iterating through all the numbers, the heap contains the `k` largest elements of the array.
- The root of the min-heap is the smallest of these `k` elements, which is the k-th largest element overall. Return this element.

## Quickselect (Partition-based Selection)
The most efficient approach in terms of average time complexity is the Quickselect algorithm. It's a selection algorithm that finds the k-th smallest (or largest) element in an unordered array by adapting the partitioning strategy of Quicksort.
**Time:** Average Case: O(N * L). On average, each partition step reduces the search space by half. Worst Case: O(N^2 * L). This occurs with consistently poor pivot choices, but is highly unlikely with a randomized pivot. · **Space:** O(1) for the iterative implementation. A recursive implementation would use O(log N) space on average for the recursion stack, and O(N) in the worst case.
**Pros:** Optimal average time complexity.; It is an in-place algorithm, leading to O(1) auxiliary space for the iterative version.
**Cons:** More complex to implement correctly from scratch compared to sorting or using a library heap.; Has a worst-case time complexity of O(N^2 * L), although this is rare with a good pivot strategy (like randomization).
### Explanation
Quickselect works by recursively partitioning the array around a pivot element. Unlike Quicksort, which recurses into both sides of the partition, Quickselect only recurses into the side that contains the element we are looking for. This reduces the average time complexity from O(N log N) to O(N).

We want to find the k-th largest element, which is equivalent to finding the (n-k)-th smallest element. Let `targetIndex = n - k`. The algorithm repeatedly partitions a portion of the array. After each partition, the pivot element is in its final sorted position. By comparing this position with our `targetIndex`, we can discard the part of the array that we know does not contain our target element and continue the search in the relevant part. Using a random pivot is crucial to avoid the worst-case scenario where the partitions are extremely unbalanced.

An iterative implementation is often preferred to avoid deep recursion stacks.

```java
import java.util.Random;

class Solution {
    public String kthLargestNumber(String[] nums, int k) {
        int n = nums.length;
        int targetIndex = n - k;
        int left = 0;
        int right = n - 1;
        Random random = new Random();

        while (left <= right) {
            // Choose a random pivot to avoid worst-case performance
            int pivotIndex = left + random.nextInt(right - left + 1);
            int finalPivotIndex = partition(nums, left, right, pivotIndex);

            if (finalPivotIndex == targetIndex) {
                return nums[targetIndex];
            } else if (finalPivotIndex < targetIndex) {
                left = finalPivotIndex + 1;
            } else { // finalPivotIndex > targetIndex
                right = finalPivotIndex - 1;
            }
        }
        return ""; // Should not be reached
    }

    private int partition(String[] nums, int left, int right, int pivotIndex) {
        String pivotValue = nums[pivotIndex];
        swap(nums, pivotIndex, right); // Move pivot to the end
        int storeIndex = left;

        for (int i = left; i < right; i++) {
            if (compare(nums[i], pivotValue) < 0) {
                swap(nums, storeIndex, i);
                storeIndex++;
            }
        }
        swap(nums, right, storeIndex); // Move pivot to its final sorted place
        return storeIndex;
    }

    private int compare(String a, String b) {
        if (a.length() != b.length()) {
            return a.length() - b.length();
        }
        return a.compareTo(b);
    }

    private void swap(String[] nums, int i, int j) {
        String temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
```
### Algorithm
- The goal is to find the element that would be at index `n - k` in a sorted array. Let's call this `targetIndex`.
- Implement a `partition` function that takes a subarray, chooses a pivot, and rearranges the elements such that elements smaller than the pivot are on its left and larger elements are on its right. It returns the pivot's final index.
- Use a loop that narrows down the search range `[left, right]`:
  - Choose a random pivot within the current range to ensure average-case performance.
  - Partition the subarray around the pivot and get its final index, `p`.
  - If `p == targetIndex`, the element is found. Return `nums[p]`.
  - If `p < targetIndex`, the desired element is in the right subarray. Update `left = p + 1`.
  - If `p > targetIndex`, the desired element is in the left subarray. Update `right = p - 1`.
- The loop terminates when the pivot's final index equals `targetIndex`.

# Solutions
### Java

```java
class Solution {
public
  String kthLargestNumber(String[] nums, int k) {
    Arrays.sort(nums, (a, b)->a.length() == b.length()
                          ? b.compareTo(a)
                          : b.length() - a.length());
    return nums[k - 1];
  }
}

```

### Python

```python
class Solution:
    def kthLargestNumber(self, nums: List[str], k: int) -> str: def cmp(a, b): if len(a) != len(b): return len(b) - len(a) return 1 if b > a else - 1 nums . sort(key=cmp_to_key(cmp)) return nums[k - 1]

```

### CPP

```cpp
class Solution {
public:
  string kthLargestNumber(vector<string> &nums, int k) {
    auto cmp = [](const string &a, const string &b) {
      return a.size() == b.size() ? a > b : a.size() > b.size();
    };
    sort(nums.begin(), nums.end(), cmp);
    return nums[k - 1];
  }
};

```