Find the Kth Largest Integer in the Array

You are given an array of strings nums where each string represents a non-negative integer. You are also given an integer k. Return the string that represents the kth largest integer in the array.

This is LeetCode 1985: Find the Kth Largest Integer in the Array. It looks like a simple sorting problem at first glance, but there is a twist: the numbers can be extremely large (up to 100 digits), so you cannot convert them to standard integer types in most languages. You need to compare them as strings using a custom comparator.

Example: nums = ["3", "6", "7", "10"], k = 2. The answer is "7" because the sorted order (ascending) is ["3", "6", "7", "10"], and the 2nd largest is "7".

Why this problem is tricky

If these were regular integers, you would just sort the array and pick the element at index n - k. But these are strings. Sorting strings lexicographically gives the wrong answer because lexicographic order does not match numeric order for strings of different lengths.

Consider "10" vs "7". Lexicographically, "10" comes before "7" because the character '1' is less than '7'. But numerically, 10 is greater than 7. If you sort these strings with the default comparator, you get the wrong answer.

The fix is a custom comparison function that respects numeric ordering.

The key insight: comparing string integers

Two rules handle all cases:

1. Different lengths? The longer string represents a larger number (the problem guarantees no leading zeros except for "0" itself).
2. Same length? Compare them lexicographically. When two numeric strings have the same number of digits, character-by-character comparison gives the correct numeric ordering. "37" vs "42": '3' is less than '4', so "37" is less than "42". This matches the numeric truth.

That is the entire comparator. Length first, then lexicographic. No big-integer parsing needed.

The code

In Python, you can use functools.cmp_to_key to pass a custom comparator to the sort function:

from functools import cmp_to_key

def kth_largest_integer(nums: list[str], k: int) -> str:
    def compare(a: str, b: str) -> int:
        if len(a) != len(b):
            return len(a) - len(b)
        if a < b:
            return -1
        if a > b:
            return 1
        return 0

    nums.sort(key=cmp_to_key(compare))
    return nums[-k]

Or, even more concisely, you can leverage Python's ability to handle arbitrarily large integers:

def kth_largest_integer(nums: list[str], k: int) -> str:
    nums.sort(key=lambda x: int(x))
    return nums[-k]

The int() approach works perfectly in Python because Python integers have no size limit. In languages like Java or C++, you would need the custom comparator since the numbers can exceed 64-bit integer range. Understanding the comparator approach is more useful for interviews because it works in any language and shows deeper problem-solving.

Step-by-step walkthrough

Let's trace through the sorting process to see why the custom comparator matters and how the answer emerges.

Why not just use int() everywhere?

In Python, converting to int is the simplest path. But interviewers often ask this problem specifically to test whether you understand string comparison for large numbers. Here is why the comparator approach matters:

• Language portability. In Java, C++, or Go, you cannot fit a 100-digit number into any built-in integer type. The comparator is the only option.
• Performance. Converting a 100-digit string to a big integer is O(d) where d is the number of digits. The comparator is also O(d) per comparison. Neither is faster, but the comparator avoids allocating big-integer objects.
• Interview signal. Writing a clean comparator shows you understand how string comparison relates to numeric comparison. That is the actual skill being tested.

Complexity analysis

All approaches are dominated by the cost of sorting (or heap operations) multiplied by the cost of each comparison (O(d) for d-digit strings). The custom comparator version uses less extra space because it compares strings in place rather than creating big-integer copies.

The building blocks

This problem combines two reusable pieces:

Custom string comparison for large numbers

The comparator that checks length first, then lexicographic order. This same technique appears whenever you need to order numeric strings that exceed standard integer ranges. Problems involving large number arithmetic, version number comparison, or custom sort orders all rely on the same idea.

The template:

def compare_numeric_strings(a: str, b: str) -> int:
    if len(a) != len(b):
        return len(a) - len(b)
    if a < b:
        return -1
    if a > b:
        return 1
    return 0

Kth largest via sorting

Once you have the right comparison, finding the kth largest is just sorting and indexing. Sort in ascending order and return the element at index n - k. This is the same pattern used in Kth Largest Element, just with a different comparison function.

nums.sort(key=cmp_to_key(compare))
return nums[-k]

Edge cases to watch for

• Single element. nums = ["5"], k = 1. Return "5". Only one element, and it is the 1st largest.
• All identical. nums = ["3", "3", "3"], k = 2. Return "3". The kth largest does not require distinct values.
• Very large numbers. nums = ["123456789012345678901234567890"]. The comparator handles this fine since it only compares characters, never parses the full number.
• Leading zeros are not present. The problem guarantees no leading zeros (except "0" itself), which is what makes the length-first comparison valid. If leading zeros were allowed, you would need to strip them first.
• k equals n. You want the smallest element. Sorting still works. Return nums[0] after sorting ascending.

From understanding to recall

The core of this problem is the comparator. The sorting and indexing are standard. What you need to remember is the two-rule comparison: length first, then lexicographic. That is a small piece of logic, but under pressure it is easy to forget why lexicographic comparison alone fails for different-length strings.

Spaced repetition helps you internalize this. You write the comparator from scratch, not from memorizing the code, but from understanding the invariant: "a longer numeric string is always a larger number when there are no leading zeros." A few reps at increasing intervals and the comparator becomes automatic.

CodeBricks breaks this into a focused drill so you practice the custom comparison in isolation, separate from the sorting boilerplate. That way, when you see a problem that needs numeric string ordering, the building block fires immediately.

Related posts

• Kth Largest Element - The classic integer version of kth largest, solved with heaps and quickselect
• Group Anagrams - Another problem where the key insight is choosing the right comparison or canonical form
• Contains Duplicate - A simpler array problem that introduces the "sort and scan" building block