DSA problem
Find the Kth Largest Integer in the Array
You are given an array of strings nums and an integer k. Each string in nums represents a non-negative integer without leading zeros. Return the k-th largest integer in nums. Note that duplicate numbers should be counted distinctly — for example, if nums = ["1","2","2"], "2" is the first largest integer and the second largest integer.
The twist compared to the standard "Kth Largest" problem is that the numbers are stored as strings of potentially huge magnitude — up to 100 digits each — far exceeding the range of 64-bit integers. Parsing them into a primitive numeric type is not possible without arbitrary-precision arithmetic, and even where it is (BigInteger in Java, Python int), arithmetic on 100-digit values per comparison can be wasteful.
The crucial insight is that comparing two non-negative integers written in decimal without leading zeros can be done directly on their string representations using a simple two-step rule: first compare by length (a longer string represents a strictly larger number), and only when the lengths are equal do you compare them lexicographically (character by character from the left). This is a strict total order that exactly matches numeric comparison for the given input format.
The canonical optimal approach therefore plugs a string-numeric comparator into Quickselect. We pick the element at index n - k in the order induced by this comparator using a randomized-pivot Lomuto partition, exactly as in the integer version. Each comparison costs O(L) where L is the average string length, so the expected running time is O(n * L) — linear in the total input size — with O(1) extra space and an O(n^2 * L) worst case made vanishingly unlikely by randomized pivot selection.
Examples
nums = ["3","6","7","10"], k = 4"3"nums = ["2","21","12","1"], k = 3"2"nums = ["0","0"], k = 2"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.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.