Watch 9 video solutions for Find the Kth Largest Integer in the Array, a medium level problem involving Array, String, Divide and Conquer. This walkthrough by NeetCode has 15,347 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |