Find the Kth Largest Integer in the Array
MedPrompt
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 <= 1041 <= nums[i].length <= 100nums[i]consists of only digits.nums[i]will not have any leading zeros.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
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.sortin Java) to sort the entirenumsarray in ascending order using the custom comparator. - The k-th largest element will be at index
n - k, wherenis the length of the array. Returnnums[n - k].
Walkthrough
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.
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]; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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]; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.