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.Problem Overview: You are given an array of integers represented as strings. The goal is to return the kth largest integer. Since values can exceed normal integer limits, comparison must be done using string length first, then lexicographic order.
Approach 1: Sort and Pick Approach (O(n log n) time, O(1)–O(n) space)
The simplest solution sorts the array of numeric strings in descending numeric order and returns the element at index k-1. Because the values are stored as strings, comparison works by checking length first (longer string means larger number). If two strings have the same length, compare them lexicographically. Most languages allow custom comparators during sorting, making this approach straightforward. This method relies heavily on sorting and works well when the array size is moderate and simplicity is preferred.
Approach 2: Min-Heap (Priority Queue) Approach (O(n log k) time, O(k) space)
This approach maintains a min-heap of size k. Iterate through the array and push each numeric string into the heap using the same comparison logic (length first, then lexicographic). If the heap size exceeds k, remove the smallest element. After processing all elements, the root of the heap is the kth largest number. This approach avoids sorting the entire array and is more efficient when k is much smaller than n. It uses a heap (priority queue) to track the top k largest values.
Approach 3: Quickselect (Average O(n) time, O(1) space)
A selection algorithm similar to quicksort can partition the array around a pivot and recursively search the side containing the kth largest element. Instead of fully sorting the array, Quickselect only processes the portion that contains the target rank. Comparisons still follow the numeric string rules (length then lexicographic). This approach uses ideas from divide and conquer. While the average time complexity is linear, the worst case can degrade to O(n²) without randomized pivots.
Recommended for interviews: The min-heap solution is usually the safest choice. It demonstrates understanding of heaps and efficiently handles large datasets with O(n log k) complexity. Sorting shows clear reasoning and is often accepted in interviews, but the heap approach highlights stronger algorithmic thinking when k is small relative to n.
Sort and Pick Approach: The simplest approach is to sort the array of strings based on their numeric values (considering the differences in lengths and lexicographical order when required) and then pick the kth largest element from this sorted array. This approach takes advantage of built-in sort capabilities that can be customized for string comparison in terms of numeric values. After sorting the array in descending order, the kth element can be directly accessed.
The code uses the quicksort function qsort() with a custom comparator. The comparator first checks the lengths of the strings since a larger string length implies a larger number. If the lengths are equal, it compares the strings lexicographically but in reverse order to achieve descending sort. After sorting, it returns the kth element from the sorted array.
Time Complexity: O(n log n) due to sorting, where n is the number of elements in nums.
Space Complexity: O(1) excluding the space required for sorting.
Min-Heap Approach: This approach involves using a min-heap (or priority queue) to efficiently find the kth largest element. The idea is to maintain a heap of size k while iterating through the array of strings. By doing so, the smallest element in the heap will automatically become the kth largest once all numbers are processed. This method provides an optimal solution in terms of time complexity compared to sorting.
This C++ code uses a priority queue configured as a min-heap (due to custom comparator) where each string is inserted. If the heap exceeds size k, the smallest number is removed, ensuring the kth largest remains in the heap.
C++
Java
Python
JavaScript
Time Complexity: O(n log k), where n is the number of elements in nums.
Space Complexity: O(k), due to the heap storing k elements.
We can sort the strings in the nums array in descending order as integers, and then take the k-th element. Alternatively, we can use the quickselect algorithm to find the k-th largest integer.
The time complexity is O(n times log n) or O(n), where n is the length of the nums array. The space complexity is O(log n) or O(1).
| Approach | Complexity |
|---|---|
| Sort and Pick Approach | Time Complexity: O(n log n) due to sorting, where n is the number of elements in nums. |
| Min-Heap (Priority Queue) Approach | Time Complexity: O(n log k), where n is the number of elements in nums. |
| Sorting or Quickselect | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Pick | O(n log n) | O(1)–O(n) | Best when simplicity matters and full sorting cost is acceptable |
| Min-Heap (Priority Queue) | O(n log k) | O(k) | Efficient when k is small compared to n |
| Quickselect | Average O(n), Worst O(n²) | O(1) | Useful when you only need the kth element without sorting the entire array |
Find the Kth Largest Integer in the Array - Leetcode Weekly Contest - 1985 Python • NeetCode • 15,347 views views
Watch 8 more video solutions →Practice Find the Kth Largest Integer in the Array with our built-in code editor and test cases.
Practice on FleetCode