Find the Kth Largest Integer in the Array
Understanding the Problem
This is a standard "kth largest element" problem with one complication: the numbers are represented as strings, and they can have up to 100 digits. That is far beyond what a long or even a 64-bit integer can hold, which maxes out at about 19 digits.
So we cannot convert these strings to integers and compare them directly. We need a comparison that works on the string representation itself. Because there are no leading zeros, comparing two numeric strings is direct: a longer string always represents a larger number, and strings of equal length can be compared lexicographically, character by character.
Unlike some "kth largest" problems, duplicates here count as separate entries. For ["2","2","1"] with k=2, the answer is "2" (the second copy), not "1".
Key Constraints:
1 <= k <= nums.length <= 10^4→ With n up to 10,000, an O(n log n) sort is well within limits, and an O(n log k) heap or O(n) average quickselect are also options.1 <= nums[i].length <= 100→ Numbers can have up to 100 digits, which rules out converting to any integer type. Every comparison is a string comparison costing O(m) where m is the string length.- No leading zeros → A string with more characters is always the larger number, and for equal-length strings lexicographic order matches numeric order. This is what makes string comparison correct without conversion.
Approach 1: Sorting
Intuition
Sort the entire array of numeric strings, then pick the kth element from the end. This needs a custom comparator. A plain lexicographic sort ranks "9" above "10" (because '9' > '1'), which is numerically wrong. Comparing lengths first fixes that: with no leading zeros, a longer string is always a larger number, and for equal-length strings lexicographic order matches numeric order.
Algorithm
- Sort the array using a custom comparator that compares two numeric strings: if lengths differ, the longer string is greater; if lengths are equal, compare lexicographically.
- After sorting in ascending order, the kth largest element sits at index
n - k. - Return that element.
Example Walkthrough
Code
- Time Complexity: O(n log n * m). Sorting performs O(n log n) comparisons, and each comparison of two strings takes O(m) time where m is the maximum string length (up to 100).
- Space Complexity: O(m) to O(n * m). Depends on the sorting implementation. In-place sorts use O(log n) stack space for recursion. Some language runtimes allocate additional space for stable sorting.
Sorting orders the entire array even though we only need one position. The next approach tracks the top k elements during a single scan and discards the rest.
Approach 2: Min-Heap of Size K
Intuition
Instead of sorting everything, use a min-heap (priority queue) that holds at most k elements. Add each string to the heap. When the heap grows beyond size k, remove the smallest element. After processing all elements, the heap holds exactly the k largest values, and the smallest of those (the heap top) is the kth largest overall.
A min-heap fits here because the element we need fast access to is the smallest of the current top-k. That element is both the eviction candidate when a larger value arrives and the final answer.
The invariant is that after processing any prefix of the array, the heap contains the k largest values seen so far (or all of them if fewer than k have been seen). When a new value arrives and the heap is full, it is only discarded if it is smaller than the current minimum, so it could not belong to the top-k. Any value larger than the minimum displaces it, which can only improve the set. After the full pass, the heap holds the k largest values overall, and its minimum is the kth largest.
Algorithm
- Create a min-heap with a custom comparator that compares numeric strings (shorter string is smaller; for equal lengths, lexicographically smaller is smaller).
- Iterate through each string in the array:
- Add the string to the heap.
- If the heap size exceeds k, remove the minimum (top of the min-heap).
- After processing all strings, the top of the heap is the kth largest element. Return it.
Example Walkthrough
Code
- Time Complexity: O(n log k * m). We process n elements. Each heap insertion or removal is O(log k), and each comparison within the heap costs O(m) for string comparison. When k is much smaller than n, this is significantly better than full sorting.
- Space Complexity: O(k * m). The heap stores at most k strings, each up to length m.
The heap maintains an ordered structure of k elements throughout the scan, though we only read one value at the end. The next approach partitions the array around a pivot to locate the kth largest directly, without keeping any element ordered.
Approach 3: Quickselect
Intuition
Quickselect is the selection-algorithm analog of quicksort. Instead of sorting the entire array, it recurses only into the partition that contains the target index. On average each step reduces the search range by a constant factor, giving O(n) expected time.
The mechanism: pick a pivot and partition the array so smaller elements end up on one side and larger ones on the other, with the pivot in its final sorted position. If the target index falls in the left section, recurse left; if it falls in the right section, recurse right; if it lands among the elements equal to the pivot, return the pivot.
Worst-case performance is O(n^2), which occurs when the chosen pivots repeatedly split off only one element. Choosing the pivot at random makes a long run of such splits improbable, so the expected running time stays linear.
Algorithm
- Define a comparator that compares numeric strings (by length first, then lexicographically).
- Set the target index to
n - k(the kth largest in ascending order). - Use the quickselect algorithm:
- Pick a random pivot.
- Partition the array into elements less than, equal to, and greater than the pivot (three-way partition).
- If the target index falls in the "less than" section, recurse left.
- If it falls in the "equal" section, return the pivot.
- Otherwise, recurse right.
- Return the element at the target index after partitioning completes.
Example Walkthrough
Code
- Time Complexity: O(n m) average, O(n^2 m) worst case. On average, each partition halves the search space: n + n/2 + n/4 + ... = O(n). Each comparison costs O(m). With random pivot selection, the probability of hitting worst case is negligible.
- Space Complexity: O(log n) average for recursion stack, O(n) worst case. The recursion depth matches the number of partition steps. On average this is O(log n), but a degenerate pivot sequence could cause O(n) depth.