MediumNo. 1985
Find the Kth Largest Integer in the Array — LeetCode 1985 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Array, String, Divide and Conquer, Quickselect, Sorting, Heap (Priority Queue)
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given an array of strings nums and an integer k. Each string in nums represents an integer without leading zeros.
Example
- 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"].
Python solution
class Solution:
def kthLargestNumber(self, nums: List[str], k: int) -> str:
return nlargest(k, nums, key=lambda x: int(x))[k - 1]Complexity
- Time
- O(n × log n) or O(n), where n is the length of the nums array
- Space · auxiliary
- O(log n) or O(1)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1985. Find the Kth Largest Integer in the Array is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2343 | Query Kth Smallest Trimmed Number | Medium |
| 0215 | Kth Largest Element in an Array | Medium |
| 0973 | K Closest Points to Origin | Medium |
| 1738 | Find Kth Largest XOR Coordinate Value | Medium |
| 0218 | The Skyline Problem | Hard |
| 0912 | Sort an Array | Medium |
Frequently asked questions
- How hard is LeetCode 1985. Find the Kth Largest Integer in the Array?
LeetCode 1985. Find the Kth Largest Integer in the Array is rated Medium on LeetCode.
- What topics does LeetCode 1985. Find the Kth Largest Integer in the Array cover?
LeetCode 1985. Find the Kth Largest Integer in the Array is tagged Array, String, Divide and Conquer, Quickselect, Sorting and Heap (Priority Queue) on LeetCode.