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
- The numbers can have 100 digits, so they must be compared as strings, not converted to integers (though Python's big integers would work).
- A numeric comparison of digit strings is equivalent to comparing
(length, lexicographic value). - So sort by that composite key descending and take the
k-th. - A size-
kmin-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=Truewith the heap variant: the heap is a min-heap of theklargest, 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.