Kth Largest Element in an Array
Kth Largest Element in an Array:
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
You must solve it in O(n) time complexity.
Example 1:
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Example 2:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Constraints:
1 <= k <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
Try this Problem on your own or check similar problems:
Solution:
- Java
- JavaScript
- Python
- C++
class Solution {
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
quickselect(nums, 0, n - 1, n - k );
return nums[n - k];
}
public void quickselect(int[] elements, int left, int right, int kSmallest) {
// base case: the array contains only one element
if (left == right) return;
// select a random pivot_index
Random randomNum = new Random();
int pivot = left + randomNum.nextInt(right - left);
// find the pivot position in a sorted array
pivot = partition(elements, left, right, pivot);
// if the pivot is in its final sorted position
if (kSmallest == pivot) {
return;
} else if (kSmallest < pivot) {
// go left, pivot is to large
quickselect(elements, left, pivot - 1, kSmallest);
} else {
// go right
quickselect(elements, pivot + 1, right, kSmallest);
}
}
public int partition(int[] elements, int left, int right, int pivot) {
int pivotValue = elements[pivot];
// 1. move pivot to end
swap(elements, pivot, right);
int tempIndex = left;
// 2. move all less frequent elements to the left
for (int i = left; i <= right; ++i) {
if (elements[i] < pivotValue) {
swap(elements, tempIndex, i);
tempIndex++;
}
}
// you can think of tempIndex as writter, while i is iterator starting from left
// if we have a smaller number we move it to the left side and increment the writter
// otherwise we just keep on looping over the array
// 3. move pivot to its final place
swap(elements, tempIndex, right);
return tempIndex;
}
public void swap(int[] elements, int a, int b) {
int tmp = elements[a];
elements[a] = elements[b];
elements[b] = tmp;
}
}
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function (nums, k) {
const n = nums.length;
quickselect(nums, 0, n - 1, n - k);
return nums[n - k];
};
function quickselect(elements, left, right, kSmallest) {
if (left === right) return;
const pivot = partition(
elements,
left,
right,
left + Math.floor(Math.random() * (right - left + 1))
);
if (kSmallest === pivot) {
return;
} else if (kSmallest < pivot) {
quickselect(elements, left, pivot - 1, kSmallest);
} else {
quickselect(elements, pivot + 1, right, kSmallest);
}
}
function partition(elements, left, right, pivot) {
const pivotValue = elements[pivot];
swap(elements, pivot, right);
let tempIndex = left;
for (let i = left; i <= right; i++) {
if (elements[i] < pivotValue) {
swap(elements, tempIndex, i);
tempIndex++;
}
}
swap(elements, tempIndex, right);
return tempIndex;
}
function swap(elements, a, b) {
const temp = elements[a];
elements[a] = elements[b];
elements[b] = temp;
}
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
n = len(nums)
self.quickselect(nums, 0, n - 1, n - k)
return nums[n - k]
def quickselect(self, elements, left, right, kSmallest):
if left == right:
return
pivot = self.partition(elements, left, right, left + random.randint(0, right - left))
if kSmallest == pivot:
return
elif kSmallest < pivot:
self.quickselect(elements, left, pivot - 1, kSmallest)
else:
self.quickselect(elements, pivot + 1, right, kSmallest)
def partition(self, elements, left, right, pivot):
pivotValue = elements[pivot]
elements[pivot], elements[right] = elements[right], elements[pivot]
tempIndex = left
for i in range(left, right):
if elements[i] < pivotValue:
elements[i], elements[tempIndex] = elements[tempIndex], elements[i]
tempIndex += 1
elements[tempIndex], elements[right] = elements[right], elements[tempIndex]
return tempIndex
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
quickselect(nums, 0, n - 1, n - k);
return nums[n - k];
}
private:
void quickselect(vector<int>& elements, int left, int right, int kSmallest) {
if (left == right) return;
int pivot = partition(elements, left, right, left + rand() % (right - left + 1));
if (kSmallest == pivot) {
return;
} else if (kSmallest < pivot) {
quickselect(elements, left, pivot - 1, kSmallest);
} else {
quickselect(elements, pivot + 1, right, kSmallest);
}
}
int partition(vector<int>& elements, int left, int right, int pivot) {
int pivotValue = elements[pivot];
swap(elements[pivot], elements[right]);
int tempIndex = left;
for (int i = left; i <= right; ++i) {
if (elements[i] < pivotValue) {
swap(elements[i], elements[tempIndex]);
tempIndex++;
}
}
swap(elements[tempIndex], elements[right]);
return tempIndex;
}
};
Time/Space Complexity:
- Time Complexity: O(n)
- Space Complexity: O(log n)
Explanation:
We utilize the same quick select approach as we did in Top K Frequent Elements. This time is just easier since we don't have to create additional maps and arrays, we simply perform it on the input array. Note that in this implementation we're searching for the kth smallest number, but find kth largest number can be easily transformed into this problem. Since if we have 2nd largest number in array [1,2,3,4,5] (this case it's 4), it is also the fourth smallest number in the array n-2 = 3, index = 3 since 0-indexed array. We could however modify the partition function to place all larger numbers than pivot on the left side (instead placing smaller number), and then we could just search for kLargest == pivot. For the space complexity of quick select we have O(log n) to account for the stack depth for the recursive call of quickselect (since we're halving the search space each time, the number of times we can do that is logarithmic).