Find the Kth Largest Integer in the Array

medium array string heap quickselect

Problem

Given an array nums of strings representing non-negative integers (possibly very large) and an integer k, return the kth largest integer in nums. Numbers are compared by numeric magnitude — first by length, then by lexicographic order.

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

Output"3"

Sorted descending: 10, 7, 6, 3. The 4th element is 3.

nums (comma-separated numeric strings)

import heapq

def kth_largest_number(nums, k):
    def key(s):
        return (len(s), s)
    heap = []
    for x in nums:
        heapq.heappush(heap, (len(x), x))
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0][1]

// Min-heap keyed by (length, lex). We keep size at most k.
function kthLargestNumber(nums, k) {
  const heap = [];
  const cmp = (a, b) => a.length !== b.length ? a.length - b.length : (a < b ? -1 : a > b ? 1 : 0);
  const up = i => { while (i > 0) { const p = (i-1)>>1; if (cmp(heap[i], heap[p]) < 0) { [heap[i],heap[p]]=[heap[p],heap[i]]; i=p; } else break; } };
  const down = i => { const n = heap.length; while (true) { let l=2*i+1, r=2*i+2, s=i; if (l<n && cmp(heap[l],heap[s])<0) s=l; if (r<n && cmp(heap[r],heap[s])<0) s=r; if (s===i) break; [heap[i],heap[s]]=[heap[s],heap[i]]; i=s; } };
  for (const x of nums) {
    heap.push(x); up(heap.length - 1);
    if (heap.length > k) { heap[0] = heap.pop(); down(0); }
  }
  return heap[0];
}

class Solution {
    public String kthLargestNumber(String[] nums, int k) {
        PriorityQueue<String> pq = new PriorityQueue<>((a, b) ->
            a.length() != b.length() ? a.length() - b.length() : a.compareTo(b));
        for (String x : nums) {
            pq.offer(x);
            if (pq.size() > k) pq.poll();
        }
        return pq.peek();
    }
}

string kthLargestNumber(vector<string>& nums, int k) {
    auto cmp = [](const string& a, const string& b) {
        if (a.size() != b.size()) return a.size() > b.size();
        return a > b;
    };
    priority_queue<string, vector<string>, decltype(cmp)> pq(cmp);
    for (auto& x : nums) {
        pq.push(x);
        if ((int)pq.size() > k) pq.pop();
    }
    return pq.top();
}

Explanation

To find the kth largest value, we don't need to sort everything — we just keep a min-heap of the k biggest seen so far. Once that heap holds exactly k items, its smallest (the top) is by definition the kth largest overall.

The numbers are stored as strings and can be huge, so we compare them by numeric magnitude: first by length, then alphabetically. The code pushes the key (len(x), x) so a longer string (bigger number) outranks a shorter one, and equal-length strings fall back to normal string order.

For each value we heappush it, then if the heap grew past size k we heappop the smallest. This throws away values too small to be in the top k, keeping the heap at size k with the k largest survivors.

At the end, heap[0] is the smallest of those k largest values — exactly the kth largest. We return its string part heap[0][1].

Example: nums = ["3", "6", "7", "10"], k = 4. Here k equals the array size, so the heap keeps all four and its top is the smallest number, "3", which is the 4th largest.

Time: O(n log k) Space: O(k)