medium

Find the Kth Largest Integer in the Array

Find the kth largest number-string using quickselect with a digit-length comparator.

1. Define the problem

Find the Kth Largest Integer in the Array

Given an array of strings nums where each string represents a non-negative integer, and an integer k, return the string representing the kth largest integer in the array. The integers can be far larger than a normal numeric type can safely hold, so compare them by digit count, then lexicographically instead of converting them to a number. Use quickselect with that custom comparison, exactly like the numeric version — only how two values compare changes.

Constraints

  • 1 ≤ k ≤ nums.length ≤ 104
  • 1 ≤ numsi.length ≤ 100
  • numsi consists of only digits
  • numsi will not have any leading zeros

Example

Inputnums = ["3", "6", "7", "10"], k = 4
Output"3"

Explanation As integers the values are 3, 6, 7, 10. Sorted descending: 10, 7, 6, 3 — the 4th largest is 3.

2. Know the words first

In plain terms

Digit-count comparison
For non-negative integers written without leading zeros, a longer string is always the larger number; equal-length strings compare the same way as plain string comparison.
3. Visualize the solution

Quickselect with a digit-count comparator instead of numeric less-than

Quickselect with a digit-count comparator instead of numeric less-than
Statusstart

Pivot = "1" (length 1, smallest). Partition all four numbers around it.

What happens in this step

array: ["2", "21", "12", "1"], k = 3 → target index = length - k = 4 - 3 = 1
pivot = arr[3] = "1" (length 1)

Comparison rule: shorter string = smaller number first; equal-length strings fall back to plain string comparison.
Step 1 of 4

Steps to visualize

  1. Compare two number strings by length first — the longer string is always the larger number.
  2. If lengths are equal, compare them exactly like regular strings.
  3. Use that comparator inside the same partition step as ordinary quickselect.
  4. Recurse into only the side of the partition that contains the target rank.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Quickselect with a digit-count comparator instead of numeric less-than
Statusstart

Pivot = "1" (length 1, smallest). Partition all four numbers around it.

What happens in this step

array: ["2", "21", "12", "1"], k = 3 → target index = length - k = 4 - 3 = 1
pivot = arr[3] = "1" (length 1)

Comparison rule: shorter string = smaller number first; equal-length strings fall back to plain string comparison.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function findKthLargestNumber(nums, k) {
  const target = nums.length - k;

  function lessThan(a, b) {
    if (a.length !== b.length) return a.length < b.length;
    return a < b;
  }

  function partition(arr, lo, hi) {
    const randomIndex = lo + Math.floor(Math.random() * (hi - lo + 1));
    [arr[randomIndex], arr[hi]] = [arr[hi], arr[randomIndex]];

    const pivot = arr[hi];
    let i = lo;

    for (let j = lo; j < hi; j++) {
      if (lessThan(arr[j], pivot)) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++;
      }
    }

    [arr[i], arr[hi]] = [arr[hi], arr[i]];
    return i;
  }

  function quickSelect(arr, lo, hi) {
    if (lo === hi) return arr[lo];

    const p = partition(arr, lo, hi);
    if (p === target) return arr[p];
    if (p < target) return quickSelect(arr, p + 1, hi);
    return quickSelect(arr, lo, p - 1);
  }

  return quickSelect(nums, 0, nums.length - 1);
}
Time
O(n) average, O(n²) worst case
Space
O(log n) average for the recursion stack
6. Test cases

Test cases

InputExpectedCovers
nums = ["3", "6", "7", "10"], k = 4"3"example from the docstring
nums = ["2", "21", "12", "1"], k = 3"2"mixed digit-count values where numeric and lexicographic order disagree
nums = ["5"], k = 1"5"smallest valid input, a single element
nums = ["1", "100", "11"], k = 2"11"values whose digit counts differ from each other
nums = ["5", "5", "5"], k = 2"5"every value identical
nums = ["0", "1", "2"], k = 3"0"zero as a valid non-negative integer, k asks for the smallest
nums = ["9", "999999999999999999999", "1000000000000000000000"], k = 1"1000000000000000000000"numbers far too large for a safe numeric comparison, only digit-count ordering works

Keep reading