Find the Kth Largest Integer in the Array

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.

Similar Problems

• Kth Largest Element in an Array

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.

We need to custom our comparator since the default comparator is string comparator which compares by lexicographically order, it means for example: “123” < “14”.

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.

Method 2 – Using Min Heap

Intuition

Rather than sorting the entire array, we can maintain a min heap of size k to efficiently keep track of the k largest numbers. This way, the smallest element in the heap is always the k-th largest overall, and we avoid unnecessary sorting of all elements.

Approach

1. Create a min heap (priority queue) with a custom comparator for string numbers (compare by length, then lexicographically).
2. Iterate through each string in nums:
   • Add the string to the heap.
   • If the heap size exceeds k, remove the smallest element.
3. After all elements are processed, the top of the heap is the k-th largest number.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public String kthLargestNumber(String[] nums, int k) {
	PriorityQueue<String> minHeap = new PriorityQueue<>((o1, o2) -> {
		if (o1.length() == o2.length()) { // If the same length then compare by their string
			return o1.compareTo(o2);
		}
		return Integer.compare(o1.length(), o2.length()); // Compare by their length
	});
	for (String num : nums) {
		minHeap.offer(num);
		if (minHeap.size() > k) {
			minHeap.poll(); // pop the minimum value in the heap
		}
	}
	return minHeap.poll();
}

Complexity

• ⏰ Time complexity: O(n * m * log k), where n is the number of strings, m is the average string length, and k is the heap size. Each insertion and removal in the heap takes O(log k), and string comparison takes O(m).
• 🧺 Space complexity: O(k * m), as the heap stores up to k strings, each of length up to m.

Method 3 – Using Max Heap

Intuition

By using a max heap, we can efficiently extract the k-th largest number by repeatedly removing the largest elements. This approach leverages the heap property to always access the largest element in constant time.

Approach

1. Create a max heap (priority queue) with a custom comparator for string numbers (compare by length, then lexicographically).
2. Add all strings from nums to the max heap.
3. Remove the largest element from the heap k-1 times.
4. The next element removed is the k-th largest number.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

String kthLargestNumberHeap(String[] nums, int k) {
	PriorityQueue<String> maxHeap = new PriorityQueue<>((a, b) -> {
		if (b.length() != a.length()) return b.length() - a.length();
		return b.compareTo(a);
	});
	for (String s : nums) {
		maxHeap.add(s);
	}
	while (k > 1) {
		maxHeap.poll();
		k--;
	}
	return maxHeap.poll();
}

Complexity

• ⏰ Time complexity: O(n * m + k * log n), where n is the number of strings, m is the average string length. Building the heap takes O(n * m), and each removal takes O(log n).
• 🧺 Space complexity: O(n * m), as the heap stores all n strings, each of length up to m.

Method 4 – Quickselect

Intuition

Quickselect is an efficient selection algorithm to find the k-th largest element without fully sorting the array. It partitions the array around a pivot, narrowing down the search space to the relevant part.

Approach

1. Shuffle the array to avoid worst-case performance.
2. Use partitioning to place the k-th largest element in its correct position.
3. Recursively partition the relevant subarray until the k-th largest is found.
4. Use a custom comparator for string numbers (compare by length, then lexicographically).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

public String kthLargestNumber(String[] nums, int K) {
	shuffle(nums);
	K--;
	int len =  nums.length, l = 0, r = len - 1;
	int mid = 0;
	while (l <= r) {
		mid = partition(nums, l, r);
		if (mid == K) break;
		if (mid < K) {
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	} 
	return nums[K];
}


private int partition(String[] nums, int l, int r) {
	String pivot = nums[l];
	while (l < r) {
		while (l < r && compare(nums[r], pivot) >= 0) r--;
		nums[l] = nums[r];
		while (l < r && compare(nums[l], pivot) <= 0) l++;
		nums[r] = nums[l];
	}
	nums[l] = pivot;
	return l;
}

private int compare(String p1, String p2) {
	return p1.length() == p2.length() ? p2.compareTo(p1) : Integer.compare(p2.length(), p1.length());
}

private void shuffle(String a[]) {
	Random random = new Random();
	for(int ind = 1; ind < a.length; ind++) {
		final int r = random.nextInt(ind + 1);
		exch(a, ind, r);
	}
}

private void exch(String[] a, int i, int j) {
	final String tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
}

Complexity

• ⏰ Time complexity: O(n * m) on average, where n is the number of strings and m is the average string length. Partitioning and comparisons are linear in n, and each comparison is O(m).
• 🧺 Space complexity: O(1) additional space, as partitioning is done in-place.