Medium

Find the Kth Largest Integer in the Array

LAB

Given non-negative integers encoded as strings, return the kth largest numeric value as a string.

EXAMPLES

Example 1

Input
{
  "nums": [
    "3",
    "6",
    "7",
    "10"
  ],
  "k": 4
}

Output
"3"

FUNCTION SHAPE

nums: stringArrayk: int→string

SOLUTION NOTE

For kth largest, use a min heap of size k. When heap exceeds size k, pop the smallest. The top of the heap is the kth largest.

Reveal reference solution +

pythonREFERENCE

# Solution 1: Sort
def kthLargestNumber(self, nums: List[str], k: int) -> str:
    nums.sort(key=lambda x: int(x))
    return nums[-k]

# Solution 2: Min heap of size k
def kthLargestNumber(self, nums: List[str], k: int) -> str:
    heap = []
    for num in nums:
        heappush(heap, int(num))
        if len(heap) == k + 1:
            heappop(heap)
    return str(heap[0])

TimeO(n log k)

SpaceO(k)

Open on LeetCode ↗