Find the Kth Largest Integer in the Array
Medium · Heap / Priority Queue · Explanation and code example
Quick Select
How it works
Quick Select is a selection algorithm based on the partitioning step of QuickSort. Instead of fully sorting the array, we only partition around a pivot and recurse into the side that contains our target index. On average, this finds the kth element in linear time. The algorithm uses median-of-three pivot selection to improve performance and avoid worst-case scenarios.
Steps
- Define comparison functions that compare strings as numbers (by length first, then lexicographically).
- Use the partition function:
- Select a
pivotusing median-of-three (first, middle, last elements). - Partition the array so elements greater than the
pivotare on the left, and smaller ones are on the right.
- Select a
- Perform quick select:
- If the search range is small (2 or fewer elements), sort them directly.
- Otherwise, partition and recurse into the appropriate half based on where index
k - 1falls relative to the pivot position.
- Return the element at index
k - 1.
Complexity
- Time complexity:
O(m * n)in average case,O(m * n ^ 2)in worst case. - Space complexity:
O(1)
Things to watch for
Converting Strings to Integers Directly
Numbers can have up to 100 digits, far exceeding the range of standard integer types (even 64-bit). Attempting to convert these strings to integers causes overflow and incorrect comparisons. Always compare strings using length-first, then lexicographic comparison.
Using Default String Comparison
Default lexicographic comparison does not work correctly for numeric strings of different lengths. For example, "9" would be considered greater than "123" lexicographically, but numerically 123 > 9. The comparator must first compare by string length, then lexicographically for equal lengths.
Off-by-One Error with k-th Element
The problem asks for the kth largest element using 1-based indexing, but arrays are 0-indexed. After sorting in descending order, the answer is at index k - 1, not k. This is a frequent source of incorrect answers.
Python code example
from typing import List
class Solution:
def greater(self, x: str, y: str) -> bool:
if len(x) != len(y):
return len(x) > len(y)
return x > y
def less(self, x: str, y: str) -> bool:
if len(x) != len(y):
return len(x) < len(y)
return x < y
def partition(self, nums: List[str], left: int, right: int) -> int:
mid = (left + right) >> 1
nums[mid], nums[left + 1] = nums[left + 1], nums[mid]
if self.less(nums[left], nums[right]):
nums[left], nums[right] = nums[right], nums[left]
if self.less(nums[left + 1], nums[right]):
nums[left + 1], nums[right] = nums[right], nums[left + 1]
if self.less(nums[left], nums[left + 1]):
nums[left], nums[left + 1] = nums[left + 1], nums[left]
pivot = nums[left + 1]
i = left + 1
j = right
while True:
while True:
i += 1
if not self.greater(nums[i], pivot):
break
while True:
j -= 1
if not self.less(nums[j], pivot):
break
if i > j:
break
nums[i], nums[j] = nums[j], nums[i]
nums[left + 1], nums[j] = nums[j], nums[left + 1]
return j
def quickSelect(self, nums: List[str], k: int) -> str:
left = 0
right = len(nums) - 1
while True:
if right <= left + 1:
if right == left + 1 and self.greater(nums[right], nums[left]):
nums[left], nums[right] = nums[right], nums[left]
return nums[k]
j = self.partition(nums, left, right)
if j >= k:
right = j - 1
if j <= k:
left = j + 1
def kthLargestNumber(self, nums: List[str], k: int) -> str:
return self.quickSelect(nums, k - 1)
C++ code example
class Solution {
public:
string kthLargestNumber(vector<string>& nums, int k) {
return quickSelect(nums, k - 1);
}
private:
bool greater(const string& x, const string& y) {
if (x.size() != y.size()) {
return x.size() > y.size();
}
return x > y;
}
bool less(const string& x, const string& y) {
if (x.size() != y.size()) {
return x.size() < y.size();
}
return x < y;
}
int partition(vector<string>& nums, int left, int right) {
int mid = (left + right) >> 1;
swap(nums[mid], nums[left + 1]);
if (less(nums[left], nums[right])) {
swap(nums[left], nums[right]);
}
if (less(nums[left + 1], nums[right])) {
swap(nums[left + 1], nums[right]);
}
if (less(nums[left], nums[left + 1])) {
swap(nums[left], nums[left + 1]);
}
string pivot = nums[left + 1];
int i = left + 1, j = right;
while (true) {
while (greater(nums[++i], pivot));
while (less(nums[--j], pivot));
if (i > j) break;
swap(nums[i], nums[j]);
}
swap(nums[left + 1], nums[j]);
return j;
}
string quickSelect(vector<string>& nums, int k) {
int left = 0, right = nums.size() - 1;
while (true) {
if (right <= left + 1) {
if (right == left + 1 && greater(nums[right], nums[left])) {
swap(nums[left], nums[right]);
}
return nums[k];
}
int j = partition(nums, left, right);
if (j >= k) {
right = j - 1;
}
if (j <= k) {
left = j + 1;
}
}
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.