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 thekth _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.

Examples

Example 1

1
2
3
4
5

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

1
2
3
4
5

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

1
2
3
4
5

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 <= 10^4
  • 1 <= nums[i].length <= 100
  • nums[i] consists of only digits.
  • nums[i] will not have any leading zeros.

Solution

Method 1 – Custom Sorting

Intuition

Since the numbers are represented as strings and can be very large, we cannot convert them to integers directly. To compare two numbers as strings, compare their lengths first; if equal, compare lexicographically. Sorting the array with this custom comparator allows us to find the k-th largest easily.

Approach

  1. Sort the array of strings in descending order using a custom comparator:
    • If the lengths differ, the longer string is larger.
    • If the lengths are equal, compare lexicographically.
  2. Return the string at index k-1 after sorting.

Code

1
2
3
4
5
6
7
8
9

class Solution {
public:
    string kthLargestNumber(vector<string>& nums, int k) {
        sort(nums.begin(), nums.end(), [](const string& a, const string& b) {
            return a.size() == b.size() ? a > b : a.size() > b.size();
        });
        return nums[k-1];
    }
};
1
2
3
4
5
6
7
8
9

func kthLargestNumber(nums []string, k int) string {
    sort.Slice(nums, func(i, j int) bool {
        if len(nums[i]) != len(nums[j]) {
            return len(nums[i]) > len(nums[j])
        }
        return nums[i] > nums[j]
    })
    return nums[k-1]
}
1
2
3
4
5
6

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];
    }
}
1
2
3
4
5
6

class Solution {
    fun kthLargestNumber(nums: Array<String>, k: Int): String {
        nums.sortWith(compareByDescending<String> { it.length }.thenByDescending { it })
        return nums[k-1]
    }
}
1
2
3
4

class Solution:
    def kthLargestNumber(self, nums: list[str], k: int) -> str:
        nums.sort(key=lambda x: (len(x), x), reverse=True)
        return nums[k-1]
1
2
3
4
5
6
7

impl Solution {
    pub fn kth_largest_number(nums: Vec<String>, k: i32) -> String {
        let mut nums = nums;
        nums.sort_by(|a, b| b.len().cmp(&a.len()).then(b.cmp(a)));
        nums[(k-1) as usize].clone()
    }
}
1
2
3
4
5
6

class Solution {
    kthLargestNumber(nums: string[], k: number): string {
        nums.sort((a, b) => b.length - a.length || b.localeCompare(a));
        return nums[k-1];
    }
}

Complexity

  • ⏰ Time complexity: O(n log n * m), where n is the number of strings and m is the average length, due to sorting with custom comparator.
  • 🧺 Space complexity: O(n * m), for storing the strings and sorting.