Skip to content

1985. Find the Kth Largest Integer in the Array 👍

  • Time: $O(n\log k)$
  • Space: $O(k)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  // Similar to 215. Kth Largest Element in an Array
  string kthLargestNumber(vector<string>& nums, int k) {
    auto compare = [](const string& a, const string& b) {
      return a.length() == b.length() ? a > b : a.length() > b.length();
    };
    priority_queue<string, vector<string>, decltype(compare)> minHeap(compare);

    for (const string& num : nums) {
      minHeap.push(num);
      if (minHeap.size() > k)
        minHeap.pop();
    }

    return minHeap.top();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  // Similar to 215. Kth Largest Element in an Array
  public String kthLargestNumber(String[] nums, int k) {
    Queue<String> minHeap = new PriorityQueue<>(
        (a, b) //
        -> a.length() == b.length() ? a.compareTo(b) : Integer.compare(a.length(), b.length()));

    for (final String num : nums) {
      minHeap.offer(num);
      if (minHeap.size() > k)
        minHeap.poll();
    }

    return minHeap.poll();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  # Similar to 215. Kth Largest Element in an Array
  def kthLargestNumber(self, nums: list[str], k: int) -> str:
    minHeap = []

    for num in nums:
      heapq.heappush(minHeap, int(num))
      if len(minHeap) > k:
        heapq.heappop(minHeap)

    return str(minHeap[0])