Find the Kth Largest Integer in the Array

• 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].

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.

1import java.util.Arrays;2import java.util.Comparator;3 4class Solution {5    public String kthLargestNumber(String[] nums, int k) {6        // Custom comparator for numerical string comparison7        Comparator<String> numComparator = (a, b) -> {8            if (a.length() != b.length()) {9                return a.length() - b.length();10            }11            return a.compareTo(b);12        };13 14        // Sort the array using the custom comparator15        Arrays.sort(nums, numComparator);16 17        // The k-th largest element is at index n-k in the sorted array18        return nums[nums.length - k];19    }20}

• 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.

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.

1import java.util.PriorityQueue;2import java.util.Comparator;3 4class Solution {5    public String kthLargestNumber(String[] nums, int k) {6        // A min-heap that will store the k largest numbers.7        // The comparator ensures that smaller numbers have higher priority.8        PriorityQueue<String> minHeap = new PriorityQueue<>((a, b) -> {9            if (a.length() != b.length()) {10                return a.length() - b.length();11            }12            return a.compareTo(b);13        });14 15        for (String num : nums) {16            minHeap.offer(num);17            // If the heap size exceeds k, remove the smallest element.18            if (minHeap.size() > k) {19                minHeap.poll();20            }21        }22 23        // The root of the heap is the k-th largest element.24        return minHeap.peek();25    }26}

• 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.

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.

1import java.util.Random;2 3class Solution {4    public String kthLargestNumber(String[] nums, int k) {5        int n = nums.length;6        int targetIndex = n - k;7        int left = 0;8        int right = n - 1;9        Random random = new Random();10 11        while (left <= right) {12            // Choose a random pivot to avoid worst-case performance13            int pivotIndex = left + random.nextInt(right - left + 1);14            int finalPivotIndex = partition(nums, left, right, pivotIndex);15 16            if (finalPivotIndex == targetIndex) {17                return nums[targetIndex];18            } else if (finalPivotIndex < targetIndex) {19                left = finalPivotIndex + 1;20            } else { // finalPivotIndex > targetIndex21                right = finalPivotIndex - 1;22            }23        }24        return ""; // Should not be reached25    }26 27    private int partition(String[] nums, int left, int right, int pivotIndex) {28        String pivotValue = nums[pivotIndex];29        swap(nums, pivotIndex, right); // Move pivot to the end30        int storeIndex = left;31 32        for (int i = left; i < right; i++) {33            if (compare(nums[i], pivotValue) < 0) {34                swap(nums, storeIndex, i);35                storeIndex++;36            }37        }38        swap(nums, right, storeIndex); // Move pivot to its final sorted place39        return storeIndex;40    }41 42    private int compare(String a, String b) {43        if (a.length() != b.length()) {44            return a.length() - b.length();45        }46        return a.compareTo(b);47    }48 49    private void swap(String[] nums, int i, int j) {50        String temp = nums[i];51        nums[i] = nums[j];52        nums[j] = temp;53    }54}