Last updated on January 5th, 2025 at 12:40 am
Here, we see a Kth Largest Element in an Array LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Divide-and-Conquer, Heap
Companies
Amazon, Apple, Bloomberg, Facebook, Microsoft, Pocketgems
Level of Question
Medium
Kth Largest Element in an Array LeetCode Solution
Table of Contents
1. 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.
Can you solve it without sorting?
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
2. Coding Pattern Used in Solution
The coding pattern used in this code is “Top ‘K’ Elements”. This pattern is commonly used when solving problems that require finding the top or bottom K elements in a dataset, such as finding the Kth largest or smallest element. The code uses a Quickselect algorithm, which is a variation of the Quicksort algorithm, to efficiently find the Kth largest element.
3. Code Implementation in Different Languages
3.1 Kth Largest Element in an Array C++
class Solution {
public:
int findKthLargest(std::vector<int>& nums, int k) {
int left = 0, right = nums.size() - 1;
while (true) {
int pivot_index = rand() % (right - left + 1) + left;
int new_pivot_index = partition(nums, left, right, pivot_index);
if (new_pivot_index == nums.size() - k) {
return nums[new_pivot_index];
} else if (new_pivot_index > nums.size() - k) {
right = new_pivot_index - 1;
} else {
left = new_pivot_index + 1;
}
}
}
private:
int partition(std::vector<int>& nums, int left, int right, int pivot_index) {
int pivot = nums[pivot_index];
std::swap(nums[pivot_index], nums[right]);
int stored_index = left;
for (int i = left; i < right; i++) {
if (nums[i] < pivot) {
std::swap(nums[i], nums[stored_index]);
stored_index++;
}
}
std::swap(nums[right], nums[stored_index]);
return stored_index;
}
};
3.2 Kth Largest Element in an Array Java
public class Solution {
public int findKthLargest(int[] nums, int k) {
int left = 0, right = nums.length - 1;
Random rand = new Random();
while (true) {
int pivot_index = left + rand.nextInt(right - left + 1);
int new_pivot_index = partition(nums, left, right, pivot_index);
if (new_pivot_index == nums.length - k) {
return nums[new_pivot_index];
} else if (new_pivot_index > nums.length - k) {
right = new_pivot_index - 1;
} else {
left = new_pivot_index + 1;
}
}
}
private int partition(int[] nums, int left, int right, int pivot_index) {
int pivot = nums[pivot_index];
swap(nums, pivot_index, right);
int stored_index = left;
for (int i = left; i < right; i++) {
if (nums[i] < pivot) {
swap(nums, i, stored_index);
stored_index++;
}
}
swap(nums, right, stored_index);
return stored_index;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
3.3 Kth Largest Element in an Array JavaScript
var findKthLargest = function(nums, k) {
const partition = (left, right, pivotIndex) => {
const pivot = nums[pivotIndex];
[nums[pivotIndex], nums[right]] = [nums[right], nums[pivotIndex]];
let storedIndex = left;
for (let i = left; i < right; i++) {
if (nums[i] < pivot) {
[nums[storedIndex], nums[i]] = [nums[i], nums[storedIndex]];
storedIndex++;
}
}
[nums[right], nums[storedIndex]] = [nums[storedIndex], nums[right]];
return storedIndex;
};
let left = 0, right = nums.length - 1;
while (true) {
const pivotIndex = left + Math.floor(Math.random() * (right - left + 1));
const newPivotIndex = partition(left, right, pivotIndex);
if (newPivotIndex === nums.length - k) {
return nums[newPivotIndex];
} else if (newPivotIndex > nums.length - k) {
right = newPivotIndex - 1;
} else {
left = newPivotIndex + 1;
}
}
};
3.4 Kth Largest Element in an Array Python
class Solution:
def findKthLargest(self, nums, k):
left, right = 0, len(nums) - 1
while True:
pivot_index = random.randint(left, right)
new_pivot_index = self.partition(nums, left, right, pivot_index)
if new_pivot_index == len(nums) - k:
return nums[new_pivot_index]
elif new_pivot_index > len(nums) - k:
right = new_pivot_index - 1
else:
left = new_pivot_index + 1
def partition(self, nums, left, right, pivot_index):
pivot = nums[pivot_index]
nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
stored_index = left
for i in range(left, right):
if nums[i] < pivot:
nums[i], nums[stored_index] = nums[stored_index], nums[i]
stored_index += 1
nums[right], nums[stored_index] = nums[stored_index], nums[right]
return stored_index
4. Time and Space Complexity
| Time Complexity(Balanced Tree) | Time Complexity(Unbalanced Tree) | Space Complexity(Balanced Tree) | Space Complexity (Unbalanced Tree) | |
| C++ | O(n) | O(n²) | O(n) | O(1) |
| Java | O(n) | O(n²) | O(n) | O(1) |
| JavaScript | O(n) | O(n²) | O(n) | O(1) |
| Python | O(n) | O(n²) | O(n) | O(1) |
- Random Pivot Selection: The use of a random pivot helps reduce the likelihood of encountering the worst-case time complexity.
- In-Place Partitioning: The algorithm modifies the input array directly, which is why the space complexity is O(1).
- Iterative vs Recursive: While the C++, Java, and JavaScript implementations use an iterative approach, the Python implementation uses recursion for partitioning. However, this does not affect the overall space complexity significantly since the recursion depth is limited to O(log n) on average.