Problem statement
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.
Problem statement taken from: https://leetcode.com/problems/Kth-largest-element-in-an-array.
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
Solutions for Kth Largest Element in an Array
Approach 1: Bubble sort
We can use Bubble sort to find the Kth largest element in an array.
- We modify the Bubble sort to run the outer loop at most K times.
- At the end of the last loop, print the K - 1 th element.
A C++ snippet of this approach is as follows:
// A function to implement bubble sort
void bubbleSort(vector<int>& nums, int n){
int i, j;
// run the outer loop k - 1 times
for (i = 0; i < k; i++)
for (j = 0; j < n - i - 1; j++)
if (nums[j] > nums[j + 1])
swap(nums[j], nums[j + 1]);
return nums[k - 1];
}
The time complexity of Bubble sort is O(n ^ 2). But in this case, we are running the outer loop k times. The time complexity of this approach is O(n * k).
We are not using additional space, so the space complexity is O(1).
Approach 2: Sorting
The naive approach is to sort the given array in descending order and return the k - 1 index (0 – Based indexing) element.
A C++ snippet of the above approach looks as below:
// C++ code for K largest elements in an array
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
sort(nums, nums + n, greater<int>());
return nums[k - 1];
}
The time complexity of this approach is O(n * log(n)) and the space complexity is O(1).
Approach 3: Min-Heap
We create a Min Heap of size K and compare the root of the Min Heap with other elements on the array. If the element is greater than the root, we swap the values and heapify the heap.
We need to execute the following steps to find the Kth largest element in an array:
- Build a Min Heap for the first k elements of the array: nums[0] to nums[k - 1].
- Iterater over the remaining elements from nums[k] to nums[n - 1].
- Compare the array element with the root of the heap.
- If the element is greater than the root, heapify the heap else, do nothing.
- After the above steps are done, our Min heap has the K largest elements of the array, and the root is the Kth largest element.
A C++ snippet of this approach is as follows:
int swap(int& x, int& y) {
int temp = x;
x = y;
y = temp;
}
// Min Heap Class
class MinHeap {
int size;
int* arr;
public:
MinHeap(int size, int input[]);
void heapify(int i);
void buildHeap();
};
MinHeap::MinHeap(int size, int input[]) {
this->size = size;
this->arr = input;
buildHeap();
}
// Min Heapify function, that assumes
// 2 * i + 1 and 2 * i + 2 are min heap and
// fix min heap property for i
void MinHeap::heapify(int i) {
// if Leaf Node, simply return
if (i >= size / 2)
return;
int smallest;
// index of left node
int left = 2 * i + 1;
// index of right node
int right = 2 * i + 2;
// Select minimum from left node and
// current node i, and store the minimum
// index in smallest variable
smallest = arr[left] < arr[i] ? left : i;
// If right child exist, compare and
// update the smallest variable
if (right < size)
smallest = arr[right] < arr[smallest] ? right : smallest;
// If Node i violates the min heap
// property, swap current node i with
// smallest to fix the min-heap property
// and recursively call heapify for node smallest.
if (smallest != i) {
swap(arr[i], arr[smallest]);
heapify(smallest);
}
}
// Build Min Heap
void MinHeap::buildHeap() {
// Calling Heapify for all non leaf nodes
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(i);
}
}
int findKthLargest(vector<int>& nums[], int size, int k) {
// create Min Heap for given array with only k elements
MinHeap* m = new MinHeap(k, nums);
// Loop For each element in array
// after the kth element
for (int i = k; i < size; i++) {
// if current element is smaller
// than minimum element, do nothing
// and continue to next element
if (nums[0] > nums[i])
continue;
// Otherwise Change minimum element to
// current element, and call heapify to
// restore the heap property
else {
nums[0] = nums[i];
m->heapify(0);
}
}
// now min heap contains k maximum elements, print the root element as it is the
// Kth largest element of the array
return nums[0];
}
The time complexity of this approach is O(n * log k) and the space complexity is O(k).
Approach 4: Priority Queue
Instead of Min Heap, we can use a Priority queue to get the Kth largest element.
Note: A Priority Queue is implemented as Max Heap by default in C++.
We need to execute the following steps to find the Kth largest element in an array:
- Iterate over the array and insert the elements in the priority queue.
- If the queue size exceeds k, pop the element from the priority queue.
- Once we have iterated over the array, return the top element of the priority queue.
A C++ snippet of this approach is as follows:
int findKthLargest(vector<int>& nums, int k) {
// initialize priority queue
priority_queue<int, vector<int>, greater<int>> pq;
// push all the elements
for (int i = 0; i < nums.size(); i++) {
pq.push(nums[i]);
// if the queue side exceeds k, pop the top element
if (pq.size() > k) {
pq.pop();
}
}
// return the top element of the priority queue
return pq.top();
}
The time complexity of this approach is O(n * log k) and the space complexity is O(k).
Approach 5: Using a Binary Search Tree
We can create a Binary Search Tree from the array elements and get the K largest elements of the array.
We need to execute the following steps:
- Create a BST by iterating over the array elements.
- Traverse the BST in reverse inorder for K times.
- Return the Kth largest element.
A C++ snippet of this approach is as follows:
struct Node {
int data;
struct Node* left;
struct Node* right;
};
class Tree {
public:
Node* root = NULL;
void addNode(int data) {
Node* newNode = new Node();
newNode->data = data;
if (!root) {
root = newNode;
} else {
Node* cur = root;
while (cur) {
if (cur->data > data) {
if (cur->left) {
cur = cur->left;
} else {
cur->left = newNode;
return;
}
} else {
if (cur->right) {
cur = cur->right;
} else {
cur->right = newNode;
return;
}
}
}
}
}
void printGreatest(int& K, vector<int>& sol, Node* node) {
if (!node || K == 0)
return;
printGreatest(K, sol, node->right);
if (K <= 0)
return;
sol.push_back(node->data);
K--;
printGreatest(K, sol, node->left);
}
};
int findKthLargest(vector<int>& nums, int k) {
vector<int> sol;
Tree tree = new Tree();
for (int i = 0; i < nums.size(); i++) {
tree.addNode(nums[i]);
}
tree.printGreatest(k, sol, tree.root);
return sol[k - 1];
}
The time complexity of this approach is O(n * log(n)). The space complexity is O(n).
Approach 6: Using Quick Sort
We can modify the Quick Sort algorithm to find the Kth largest element. Let's check the algorithm directly.
Algorithm
// findKthLargest(vector<int>& nums, int k)
- set n = nums.size()
- if n == 1
- return nums[0]
- end if
- set l = 0, h = n - 1
target = n - k
- loop while l <= h
- set pivot = partition(nums, l, h)
- if pivot < target
- set l = pivot + 1
- else if pivot > target
- set h = pivot - 1
- else
- return nums[pivot]
- end if
- end while
- return -1
// partition(vector<int> &nums, int l, int h)
- set high = nums[h]
start = l
- loop for i = l; i < h; i++
- if nums[i] < high
- swap(nums[start], nums[i])
- start++
- end if
- end for
- swap(nums[start], nums[h])
- return start
The time complexity of the above approach is O(n * log(n)), and the space complexity is O(1).
Check out our solutions in C++, Golang, and Javascript.
C++ solution
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
// if nums size is 1 return the first element
if (n == 1) {
return nums[0];
}
int l = 0, h = n - 1;
// set target to n - k
int target = n - k;
while (l <= h) {
// set pivot with the value returned by partition function
int pivot = partition(nums, l, h);
// if the pivot is less than the target, search the right side
if (pivot < target) {
l = pivot + 1;
} else if (pivot > target) {
// if the pivot is greater than the target, search the left side
h = pivot - 1;
} else {
// if the pivot is equal to the target, return nums[pivot]
return nums[pivot];
}
}
return -1;
}
int partition(vector<int> &nums, int l, int h) {
int high = nums[h];
int start = l;
for (int i = l; i < h; i++) {
// if nums[i] is less than high, then swap nums[start] with nums[i]
if (nums[i] < high) {
swap(nums[start], nums[i]);
start++;
}
}
//swap nums[start] with nums[h]
swap(nums[start], nums[h]);
return start;
}
};
Golang solution
func findKthLargest(nums []int, k int) int {
n := len(nums)
// if nums size is 1 return the first element
if n == 1 {
return nums[0]
}
l, h := 0, n - 1
// set target to n - k
target := n - k
for l <= h {
// set pivot with the value returned by partition function
pivot := partition(nums, l, h)
// if the pivot is less than the target, search the right side
if pivot < target {
l = pivot + 1
} else if pivot > target {
// if the pivot is greater than the target, search the left side
h = pivot - 1
} else {
// if the pivot is equal to the target, return nums[pivot]
return nums[pivot]
}
}
return -1
}
func partition(nums []int, l, h int) int {
high := nums[h]
start := l
for i := l; i < h; i++ {
if nums[i] < high {
// if nums[i] is less than high, then swap nums[start] with nums[i]
nums[start], nums[i] = nums[i], nums[start]
start++
}
}
//swap nums[start] with nums[h]
nums[start], nums[h] = nums[h], nums[start]
return start
}
JavaScript solution
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
let n = nums.length;
// if nums size is 1 return the first element
if (n == 1) {
return nums[0];
}
let l = 0, h = n - 1;
// set target to n - k
let target = n - k;
while (l <= h) {
// set pivot with the value returned by partition function
let pivot = partition(nums, l, h);
// if the pivot is less than the target, search the right side
if (pivot < target) {
l = pivot + 1;
} else if (pivot > target) {
// if the pivot is greater than the target, search the left side
h = pivot - 1;
} else {
// if the pivot is equal to the target, return nums[pivot]
return nums[pivot];
}
}
return -1;
};
var partition = function(nums, l, h) {
let high = nums[h];
let start = l;
for (let i = l; i < h; i++) {
// if nums[i] is less than high, then swap nums[start] with nums[i]
if (nums[i] < high) {
[nums[start], nums[i]] = [nums[i], nums[start]];
start++;
}
}
//swap nums[start] with nums[h]
[nums[start], nums[h]] = [nums[h], nums[start]];
return start;
}
Dry Run
Let's dry-run our algorithm to see how the solution works.
Input: nums = [3, 2, 1, 5, 6, 4]
k = 2
// findKthLargest(vector<int>& nums, int k)
Step 1: n = nums.size()
= 6
Step 2: if n == 0
6 == 0
false
Step 3: l = 0
h = n - 1
= 6 - 1
= 5
target = n - k
= 6 - 2
= 4
Step 4: loop while l <= h
0 <= 5
true
pivot = partition(nums, l, h)
= partition(nums, 0, 5)
// partition(nums, 0, 5)
Step 5: high = nums[h]
= nums[5]
= 4
start = l
= 0
loop for i = l; i < h
i < h
0 < 5
true
if nums[i] < high
nums[0] < 4
3 < 4
true
swap(nums[start], nums[i])
swap(nums[0], nums[0])
nums = [3, 2, 1, 5, 6, 4]
start++
start = 1
i++
i = 1
loop for i < h
i < h
1 < 5
true
if nums[i] < high
nums[1] < 4
2 < 4
true
swap(nums[start], nums[i])
swap(nums[1], nums[1])
nums = [3, 2, 1, 5, 6, 4]
start++
start = 2
i++
i = 2
loop for i < h
i < h
2 < 5
true
if nums[i] < high
nums[2] < 4
1 < 4
true
swap(nums[start], nums[i])
swap(nums[2], nums[2])
nums = [3, 2, 1, 5, 6, 4]
start++
start = 3
i++
i = 3
loop for i < h
i < h
3 < 5
true
if nums[i] < high
nums[3] < 4
5 < 4
false
i++
i = 4
loop for i < h
i < h
4 < 5
true
if nums[i] < high
nums[4] < 4
6 < 4
false
i++
i = 5
loop for i < h
i < h
5 < 5
false
swap(nums[start], nums[h])
swap(nums[3], nums[5])
swap(5, 4)
nums = [3, 1, 2, 4, 6, 5]
return start
return 3
// findKthLargest(vector<int>& nums, int k)
Step 6: pivot = partition(nums, 0, 5)
= 3
Step 7: if pivot < target
3 < 4
true
l = pivot + 1
= 3 + 1
= 4
Step 8 loop while l <= h
4 <= 5
true
pivot = partition(nums, l, h)
= partition(nums, 4, 5)
// partition(nums, 4, 5)
Step 9: high = nums[h]
= nums[5]
= 5
start = l
= 4
loop for i = l; i < h
i < h
4 < 5
true
if nums[i] < high
nums[4] < 5
6 < 5
false
i++
i = 5
loop for i < h
5 < 5
false
swap(nums[start], nums[h])
swap(nums[4], nums[5])
swap(6, 5)
nums = [3, 1, 2, 4, 5, 6]
return start
return 4
// findKthLargest(vector<int>& nums, int k)
Step 10: pivot = partition(nums, 4, 5)
= 4
Step 11: if pivot < target
4 < 4
false
else if pivot > target
4 > 4
false
else
return nums[4]
return 5
We return the answer as 5.
Top comments (0)