Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Leetcode 1985. Find the Kth Largest Integer in the Array

Given an array of non‑negative integers encoded as decimal strings (no leading zeros) and an integer k, return the k-th largest numeric value treating duplicates as distinct. The core challenge is comparing potentially long numeric strings efficiently (compare by length then lexicographically) and selecting the k-th largest (via sorting, heap, or selection).

Asked at:

Meta

DESCRIPTION

Input:

nums = ['3', '30', '34', '5', '9'], k = 2

Output:

'30'

Explanation: Sorted in descending order: ['34', '30', '9', '5', '3']. The 2nd largest is '30'

Constraints:

1 <= nums.length <= 10^4
1 <= nums[i].length <= 1000
nums[i] consists of digits only with no leading zeros
1 <= k <= nums.length
Duplicates are treated as distinct elements

Understanding the Problem

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?

Brute Force Approach

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.

Visualization

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]

Start finding k-th largest numeric string using bubble sort

0 / 77

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n² × L) Bubble sort makes O(n²) comparisons, and each string comparison takes O(L) time where L is the average string length

Space Complexity: O(1) Bubble sort is an in-place algorithm, using only constant extra space for swapping

Building Intuition

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.

Common Mistakes

Attempting to convert strings to integers without checking for overflow - strings can represent numbers far larger than 64-bit integers can hold

Comparing strings lexicographically without considering length first - this gives wrong results like '9' > '30' when comparing character-by-character

Forgetting that duplicates count as distinct - if the array is ['5', '5', '3'] and k=2, the answer is '5' (the second occurrence), not '3'

Using inefficient sorting algorithms for large inputs - bubble sort's O(n²) complexity becomes prohibitive with thousands of elements

Not handling edge cases like k=1 (largest element) or k=n (smallest element) correctly

Optimal Solution

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.

Visualization

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]

Start: Find k-th largest numeric string

0 / 37

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n log n × L) Quicksort makes O(n log n) comparisons on average, and each string comparison takes O(L) time where L is the average string length

Space Complexity: O(log n) Quicksort uses O(log n) space for the recursion stack in the average case

What We've Learned

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.

Test Your Understanding

Why is array the right data structure for this problem?

array provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late October, 2025

Meta

Mid-level

Early October, 2025

Meta

Mid-level

Early February, 2025

Meta

Senior

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 1985. Find the Kth Largest Integer in the Array

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact