Find the Kth Largest Integer in the Array

Medium
961.

Find the Kth Largest Integer in the Array

Find the Kth Largest Integer in the Array is a medium coding problem on arrays, strings and sorting, asked in Amazon, Google and Adobe interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} nums
 * @param {number} k
 * @return {string}
 */
var kthLargestNumber = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Kth Largest Integer in the Array — Solution

Find the Kth Largest Integer in the Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find the Kth Largest Integer in the Array is a medium coding problem on arrays, strings and sorting, asked in Amazon, Google and Adobe interviews.

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.

Hints for Find the Kth Largest Integer in the Array

  1. Hint 1

    The numbers can be 100 digits long, so they cannot be parsed into a machine integer.

  2. Hint 2

    Compare two digit strings directly: a longer string is the larger number.

  3. Hint 3

    Equal lengths compare lexicographically, because the digits line up.

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

  1. Compare x and y: if the lengths differ, the longer is larger.
  2. If the lengths match, ordinary string comparison is the numeric comparison.
  3. 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]

Java

public static String kthLargestNumber(String[] nums, int k) {
    String[] sorted = nums.clone();
    Arrays.sort(sorted, (x, y) -> {
        if (x.length() != y.length()) return y.length() - x.length();
        return y.compareTo(x);
    });
    return sorted[k - 1];
}

C++

string kthLargestNumber(vector<string>& nums, int k) {
    vector<string> sorted = nums;
    sort(sorted.begin(), sorted.end(), [](const string& x, const string& y) {
        if (x.size() != y.size()) return x.size() > y.size();
        return x > y;
    });
    return sorted[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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings