Find the Kth Largest Integer in the Array — Medium Problem & Solution

nums holds non-negative integers written as strings, with no leading zeros except the number "0" itself.

Difficulty: Medium
Topics: Arrays, Strings, Sorting, Heap, Divide and Conquer
Asked at: Amazon, Google, Adobe
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

nums holds non-negative integers written as strings, with no leading zeros except the number "0" itself. Duplicates count separately, so in ["1","2","2"] the second largest is "2".

Return the k-th largest integer, as a string.

Example 1

Input: nums = ["3","6","7","10"], k = 4
Output: 3
Explanation: Sorted largest first: 10, 7, 6, 3.

Example 2

Input: nums = ["2","21","12","1"], k = 3
Output: 2
Explanation: Sorted largest first: 21, 12, 2, 1.

Example 3

Input: nums = ["0","0"], k = 2
Output: 0

Constraints

1 <= k <= nums.length <= 10^4
1 <= nums[i].length <= 100
nums[i] consists of digits only.
nums[i] has no leading zeros, except for the value "0" itself.

How to solve Find the Kth Largest Integer in the Array

Define a comparison on the strings themselves — longer wins, and equal lengths compare lexicographically — then take the k-th largest under it.

Approach

Compare x and y: if the lengths differ, the longer is larger.
If the lengths match, ordinary string comparison is the numeric comparison.
Sort descending under that rule and return the entry at index k - 1.

Why it works

Length-then-lexicographic is exactly numeric order because the inputs have no leading zeros: a longer string is a strictly larger number, and at equal length the leading digits dominate exactly as characters do. A heap of size k, or quickselect, replaces the sort for a faster asymptotic, but the comparison stays the same.

Complexity

Time — O(n log n · L) with L the digit length
Space — O(n)

Pitfalls

Parsing to a 64-bit integer overflows at 100 digits.
Plain lexicographic comparison without the length check calls "9" bigger than "10".
Duplicates are counted separately; do not de-duplicate.

Reference solution

Python

from typing import List

def kthLargestNumber(nums: List[str], k: int) -> str:
    ordered = sorted(nums, key=lambda s: (len(s), s), reverse=True)
    return ordered[k - 1]

JavaScript

var kthLargestNumber = function(nums, k) {
    var sorted = nums.slice();
    sorted.sort(function(x, y) {
        if (x.length !== y.length) return y.length - x.length;
        if (x === y) return 0;
        return x < y ? 1 : -1;
    });
    return sorted[k - 1];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue