Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Hardquick-select

Find the Kth Largest Integer in the Array

Problem (restated)

An array of integers given as strings (no leading zeros except "0", values up to 100 digits). Return the kth largest as a string.

Intuition

Same partition as LC 215, with a numeric string order: longer is larger; equal length → lexicographic. You cannot parse as a 64-bit int. Target index is still n-k.

Approaches

Quick select on numeric strings

Unverified

Time O(n · L) averageSpace O(1)

Idea. cmp(a, b): compare lengths, then the strings. Randomized partition until the pivot sits at n-k. Return that string (do not convert).

Walkthrough. ["3","6","7","10"], k=4 → smallest → "3". ["2","21","12","1"], k=3 → "2".

Trade-offs. Average O(n) comparisons, each O(L). Sorting is O(n log n · L) and simpler if n is small. Randomize the pivot. Mutates the input.

Solution

export function kthLargestNumber(nums: string[], k: number): string {
  const target = nums.length - k;
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const p = partition(nums, lo, hi);
    if (p === target) return nums[p]!;
    if (p < target) lo = p + 1;
    else hi = p - 1;
  }
  return nums[lo]!;
}

function cmp(a: string, b: string): number {
  if (a.length !== b.length) return a.length - b.length;
  return a < b ? -1 : a > b ? 1 : 0;
}

function partition(nums: string[], lo: number, hi: number): number {
  const rand = lo + Math.floor(Math.random() * (hi - lo + 1));
  [nums[rand], nums[hi]] = [nums[hi]!, nums[rand]!];
  const pivot = nums[hi]!;
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (cmp(nums[j]!, pivot) < 0) {
      [nums[i], nums[j]] = [nums[j]!, nums[i]!];
      i++;
    }
  }
  [nums[i], nums[hi]] = [nums[hi]!, nums[i]!];
  return i;
}

export function kthLargestNumber(nums: string[], k: number): string {
  const target = nums.length - k;
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const p = partition(nums, lo, hi);
    if (p === target) return nums[p]!;
    if (p < target) lo = p + 1;
    else hi = p - 1;
  }
  return nums[lo]!;
}

function cmp(a: string, b: string): number {
  if (a.length !== b.length) return a.length - b.length;
  return a < b ? -1 : a > b ? 1 : 0;
}

function partition(nums: string[], lo: number, hi: number): number {
  const rand = lo + Math.floor(Math.random() * (hi - lo + 1));
  [nums[rand], nums[hi]] = [nums[hi]!, nums[rand]!];
  const pivot = nums[hi]!;
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (cmp(nums[j]!, pivot) < 0) {
      [nums[i], nums[j]] = [nums[j]!, nums[i]!];
      i++;
    }
  }
  [nums[i], nums[hi]] = [nums[hi]!, nums[i]!];
  return i;
}

Template connection

Quick Select with a custom order. LC 215 is the integer version of the same loop.

Reflection

These are numeric strings. Compare length first, then lexicographic order. The shorter one is smaller. There is no leading zero.
Parsing to a number overflows. Quickselect partitions with this order to land on the kth largest.
k = 1 is the largest. Equal strings share a rank. Between 9 and 10, the longer one is larger.