⚡Flashcard Drill➔
NeetCode #542LC-1985MediumHeap / Priority Queue
← Back to All Problems

#542 · #1985 · Find the Kth Largest Integer in the Array(找出数组中的第 K 大整数)

📌 Problem Statement & Constraints

You are given an array of strings nums representing integers without leading zeros, and an integer k. Return the string representing the k-th largest integer. Constraints: 1 <= k <= nums.length <= 10^4, 1 <= nums[i].length <= 100.

💡 Core Algorithmic Approaches

  1. The numbers can have 100 digits, so they must be compared as strings, not converted to integers (though Python's big integers would work).
  2. A numeric comparison of digit strings is equivalent to comparing (length, lexicographic value).
  3. So sort by that composite key descending and take the k-th.
  4. A size-k min-heap would give O(n log k), but the sort is simpler and fast enough.

💻 Benchmark Python3 Implementation

class Solution:
    def kthLargestNumber(self, nums: List[str], k: int) -> str:
        # for non-negative integers without leading zeros, longer means larger;
        # equal lengths compare lexicographically
        nums.sort(key=lambda s: (len(s), s), reverse=True)
        return nums[k - 1]


# Heap variant: O(n log k), avoids the full sort
class Solution2:
    def kthLargestNumber(self, nums: List[str], k: int) -> str:
        import heapq
        h = []                             # min-heap of the k largest, as strings
        for s in nums:
            key = (len(s), s)
            if len(h) < k:
                heapq.heappush(h, (key, s))
            elif key > h[0][0]:
                heapq.heapreplace(h, (key, s))
        return h[0][1]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n) for the sort, O(n log k) for the heap.
💾 Space Complexity
O(1) beyond the input for the sort, O(k) for the heap.

⚠️ Interview Pitfalls & Follow-ups

  • Converting to int: it works in Python, but the strings are up to 100 digits and the point is the comparison rule.
  • Comparing only lexicographically: "9" would beat "10"; the length must come first.
  • Using reverse=True with the heap variant: the heap is a min-heap of the k largest, so the root is the answer.
  • Off-by-one on k: the problem is 1-indexed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems