Leetcode 1985. Find the Kth Largest Integer in the Array

Let's understand what we're being asked to do. We have an array of numeric strings like ['3', '30', '34', '5', '9'] and an integer k=2, and we need to return the 2nd largest numeric value.

Tracing through: the values in numeric order are 3, 5, 9, 30, 34. The largest is 34, the 2nd largest is 30, so we return '30'.

Important constraint: The numbers are encoded as decimal strings (no leading zeros), which means they can be arbitrarily long - far beyond what a 64-bit integer can hold! We can't just parse them to integers.

Key challenge: How do we compare numeric strings efficiently? For example, '9' is numerically greater than '30' if we compare lexicographically (character-by-character), but numerically 30 > 9. The trick is: compare by length first (longer strings represent larger numbers), then lexicographically if lengths are equal.

Edge cases to consider: What if k is larger than the array length? What if there are duplicate values (they count as distinct)? What if all strings represent the same number?

The most straightforward approach is to use a simple sorting algorithm like bubble sort with a custom comparator. Implement the numeric string comparison logic (compare by length first, then lexicographically), then repeatedly bubble the largest elements to the end of the array. After sorting in descending order, return the element at index k-1. This approach is simple to understand but inefficient for large arrays due to the quadratic time complexity of bubble sort.

def kth_largest_string(nums, k):
    """
    Find k-th largest numeric string using bubble sort.
    Compare by length first, then lexicographically.
    """
    n = len(nums)
    
    # Bubble sort in descending order
    for i in range(n):
        for j in range(n - 1 - i):
            # Compare two numeric strings
            num1 = nums[j]
            num2 = nums[j + 1]
            
            # Compare by length first
            if len(num1) < len(num2):
                should_swap = True
            elif len(num1) > len(num2):
                should_swap = False
            else:
                # Same length: compare lexicographically
                should_swap = num1 < num2
            
            # Swap if num1 is smaller (we want descending order)
            if should_swap:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    
    # Return k-th largest (index k-1)
    return nums[k - 1]

When comparing two numeric strings without leading zeros, the longer string always represents the larger number. For example, '999' (length 3) is always less than '1000' (length 4).

Only when two strings have the same length do we need to compare them character-by-character (lexicographically). For example, '345' vs '367' - both length 3, so compare: '3'='3', '4'<'6', so '345' < '367'.

This observation allows us to compare arbitrarily large numbers represented as strings in O(L) time (where L is the string length), without ever converting to integers.

This means we can handle numbers with thousands of digits - far beyond the 10^18 limit of 64-bit integers - using simple string comparison logic.

Think about how you'd compare two numbers written on paper without calculating their values:

• If one number has more digits, it's automatically larger (compare '99' vs '100')
• If they have the same number of digits, compare digit-by-digit from left to right (compare '567' vs '589' - the first difference is at position 1: '6' < '8')

This is exactly how we can compare numeric strings efficiently! Once we can compare any two strings, we can sort the entire array or use a selection algorithm to find the k-th largest.

The optimal approach uses an efficient sorting algorithm like quicksort (or built-in sort) with a custom comparator. Define a comparison function that compares two numeric strings: first by length (longer is larger), then lexicographically if lengths are equal. Sort the array in descending order using this comparator, then return the element at index k-1. Modern sorting algorithms achieve O(n log n) average time complexity, which is optimal for comparison-based sorting.

def kth_largest_numeric_string(nums, k):
    """
    Find the k-th largest numeric value from an array of numeric strings.
    Compares by length first (longer is larger), then lexicographically.
    """
    # Define custom comparator for numeric strings
    def compare_numeric_strings(a, b):
        # Compare by length first
        if len(a) != len(b):
            return len(b) - len(a)  # Longer string is larger
        # If same length, compare lexicographically
        if a < b:
            return 1  # b is larger
        elif a > b:
            return -1  # a is larger
        else:
            return 0  # Equal
    
    # Import functools for cmp_to_key
    from functools import cmp_to_key
    
    # Sort array in descending order using custom comparator
    sorted_nums = sorted(nums, key=cmp_to_key(compare_numeric_strings))
    
    # Return k-th largest element (k-1 index since 0-based)
    return sorted_nums[k - 1]

• String-as-number comparison pattern: When dealing with numeric strings that may exceed standard integer limits, compare by length first, then lexicographically - a longer numeric string is always larger (e.g., "999" < "1000"), and equal-length strings can be compared character-by-character like regular strings.
• Custom comparator design: Implement a custom comparison function that encapsulates domain-specific logic (length-then-lexicographic for numeric strings) - this keeps sorting code clean and makes the comparison logic reusable across different sorting algorithms (quicksort, heapsort, etc.).
• Heap-based selection optimization: For finding the k-th largest element, use a min-heap of size k instead of full sorting - this reduces time complexity from O(n log n) to O(n log k), which is significant when k << n (e.g., finding top 10 in a million elements).
• Avoid premature conversion pitfall: Never convert large numeric strings to integers without checking bounds - strings like "999999999999999999999" will overflow. Keep comparisons in string space throughout the algorithm to handle arbitrarily large numbers safely.
• Sorting vs selection trade-off: Recognize when partial sorting (quickselect, heap) is better than full sorting - if you only need the k-th element and k is small relative to n, selection algorithms save time; if you need all elements sorted or k ≈ n, full sorting is simpler.
• Real-world big number handling: This pattern applies to financial systems (comparing transaction amounts beyond float precision), cryptography (comparing large prime numbers), and distributed systems (comparing timestamps or IDs represented as strings) where numeric precision matters.