Find the Kth Largest Integer in the Array

LeetCode 2113 | Difficulty: Medium

Medium

Problem Description

You are given an array of strings nums and an integer k. Each string in nums represents an integer without leading zeros.

Return the string that represents the k^th* largest integer in *nums.

Note: Duplicate numbers should be counted distinctly. For example, if nums is ["1","2","2"], "2" is the first largest integer, "2" is the second-largest integer, and "1" is the third-largest integer.

Example 1:

Input: nums = ["3","6","7","10"], k = 4
Output: "3"
Explanation:
The numbers in nums sorted in non-decreasing order are ["3","6","7","10"].
The 4^th largest integer in nums is "3".

Example 2:

Input: nums = ["2","21","12","1"], k = 3
Output: "2"
Explanation:
The numbers in nums sorted in non-decreasing order are ["1","2","12","21"].
The 3^rd largest integer in nums is "2".

Example 3:

Input: nums = ["0","0"], k = 2
Output: "0"
Explanation:
The numbers in nums sorted in non-decreasing order are ["0","0"].
The 2^nd largest integer in nums is "0".

Constraints:

- `1 <= k <= nums.length <= 10^4`

- `1 <= nums[i].length <= 100`

- `nums[i]` consists of only digits.

- `nums[i]` will not have any leading zeros.

Topics: Array, String, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect

---

Approach

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 172 ms)

Metric	Value
Runtime	172 ms
Memory	54.4 MB
Date	2022-01-10

Solution

public class Solution {
    public string KthLargestNumber(string[] nums, int k) {
        Array.Sort(nums, new StringNumComparer());
    
    
    return nums[k-1];
}

public class StringNumComparer : IComparer<string>
{
    public int Compare(string x, string y)
    {
        int m = x.Length;
        int n = y.Length;
        if(m!=n) return n.CompareTo(m);
        if(x==y) return 0;
        for (int i = 0; i < m; i++)
        {
            if(x[i] == y[i]) continue;
            return (y[i]-'0').CompareTo(x[i]-'0');
        }
        return 0;
    }
}
}

📜 2 more C# submission(s)

Submission (2022-01-10) — 279 ms, 56.8 MB

public class Solution {
    public string KthLargestNumber(string[] nums, int k) {
        Array.Sort(nums, new StringNumComparer());
    
    
    return nums[k-1];
}

public class StringNumComparer : IComparer<string>
{
    public int Compare(string x, string y)
    {
        int m = x.Length;
        int n = y.Length;
        if(m!=n) return n.CompareTo(m);
        if(x==y) return x.CompareTo(y);
        for (int i = 0; i < m; i++)
        {
            if(x[i] == y[i]) continue;
            return (y[i]-'0').CompareTo(x[i]-'0');
        }
        return 0;
    }
}
}

Submission (2022-01-10) — 280 ms, 54.9 MB

public class Solution {
    public string KthLargestNumber(string[] nums, int k) {
        Array.Sort(nums, new StringNumComparer());
    
    
    return nums[k-1];
}

public class StringNumComparer : IComparer<string>
{
    public int Compare(string x, string y)
    {
        int m = x.Length;
        int n = y.Length;
        if(m!=n) return n.CompareTo(m);
        return y.CompareTo(x);
    }
}
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• LeetCode provides 4 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: If two numbers have different lengths, which one will be larger?

Hint 2: The longer number is the larger number.

Hint 3: If two numbers have the same length, which one will be larger?

Hint 4: Compare the two numbers starting from the most significant digit. Once you have found the first digit that differs, the one with the larger digit is the larger number.