# Solving Kth Largest Element in an Array

To see the question, click **here**.

**Naive Approach**

To find the kth largest element, we can first sort the array and then return the `nums.length - k`

th element.

```
// TC: O(nlogn)
// SC: O(1)
import java.util.Arrays;
class KthLargestElement {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
public static void main(String args[]) {
KthLargestElement kle = new KthLargestElement();
int[] nums = { 3, 2, 1, 5, 6, 4 };
int k = 2;
System.out.println(kle.findKthLargest(nums, k));
}
}
```

**Performance**

The time complexity of the `findKthLargest`

method is O(nlogn) because it involves sorting the input array `nums`

using the `Arrays.sort()`

method, which has a time complexity of O(nlogn). The space complexity is O(1) because the sorting is done in place and does not require any additional space proportional to the input size.

**Refined Approach**

To find the kth largest element, we will utilize a `PriorityQueue`

which in turn is a min-heap. We offer each element in the array to the min-heap, and after the offering, we will check if the size of the heap exceeds `k`

. If it does, the smallest element (which is at the top of the min-heap) is removed to ensure that the heap always contains the largest `k`

elements seen so far.

```
// TC: O(nlogk)
// SC: O(k)
import java.util.PriorityQueue;
class KthLargestElement {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
public static void main(String args[]) {
KthLargestElement kle = new KthLargestElement();
int[] nums = { 3, 2, 1, 5, 6, 4 };
int k = 2;
System.out.println(kle.findKthLargest(nums, k));
}
}
```

**Performance**

The time complexity of the `findKthLargest`

method is O(nlogk). This is because we are iterating through each element in the input array and performing operations on a priority queue of size k, which has a time complexity of O(logk) to insert and remove elements. The space complexity of the `findKthLargest`

method is O(k). This is because we use a priority queue of size k to store the k largest elements in the input array.

**Efficient Approach 1**

The concept involves a "quick select" technique similar to the "quick sort" algorithm. It's important to note that the Kth largest element in an array is equivalent to the (N – K)th smallest element. Initially, we select a "pivot" element, akin to the quick sort approach. This is achieved through a specific procedure called "partitioning." During this procedure, we compare each element with the pivot. Elements smaller than the pivot are shifted to the left, while larger ones are moved to the right. Consequently, the array is divided into two segments. We can disregard one segment and concentrate on locating the (N – K)th element in the remaining segment.

```
// TC: O(n)
// SC: O(1)
class KthLargestElement {
public int findKthLargest(int[] numbers, int k) {
k = numbers.length - k; // Convert k to index of k-th largest element
int low = 0;
int high = numbers.length - 1;
while (low < high) {
int partitionIndex = partition(numbers, low, high);
if (partitionIndex < k) {
low = partitionIndex + 1;
} else if (partitionIndex > k) {
high = partitionIndex - 1;
} else {
break;
}
}
return numbers[k];
}
private int partition(int[] numbers, int low, int high) {
int pivot = numbers[low];
int i = low;
int j = high + 1;
while (true) {
// Move i to the right until finding a number greater than or equal to the pivot
while (i < high && numbers[++i] < pivot);
// Move j to the left until finding a number less than or equal to the pivot
while (j > low && numbers[low] < numbers[--j]);
if (i >= j) {
break;
}
swap(numbers, i, j);
}
swap(numbers, low, j); // Place pivot in its correct position
return j;
}
private void swap(int[] numbers, int i, int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
public static void main(String args[]) {
KthLargestElement kle = new KthLargestElement();
int[] nums = { 3, 2, 1, 5, 6, 4 };
int k = 2;
System.out.println(kle.findKthLargest(nums, k));
}
}
```

**Performance**

The time complexity of the `findKthLargest`

method is O(n) on average. This is because the partition method is called on each iteration of the while loop, which takes O(n) time in the worst-case scenario. The average time complexity is O(n) because the partitioning process divides the array into two roughly equal parts. The space complexity of the algorithm is O(1) because it does not use any extra space that grows with the input size. The algorithm sorts the input array in place without using any additional data structures.

**Efficient Approach 2**

The range for the elements inside the array is `-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>`

. If the `nums[i]`

started from 0, we could have initialized an array of size 10^{4}+1, traversed it, and incremented the count in the index based on the element, i.e., if the element is 2, we will increment the value in index 2. We could have found the kth largest element by traversing from the back. Since we cannot have negative indices, we will create an array of size 2x10^{4}+1 so that the first 10^{4} blocks are for negative numbers and the remaining are for non-negative numbers. This method is not recommended as this can lead to significant memory usage, especially if the range of values is large.

```
// TC: O(n)
// SC: O(1)
class KthLargestElement {
public int findKthLargest(int[] nums, int k) {
int[] freq = new int[20001];
for (int num : nums)
freq[num + 10000]++;
for (int i = 20000; i >= 0; i--) {
k -= freq[i];
if (k <= 0)
return i - 10000;
}
return -1;
}
public static void main(String args[]) {
KthLargestElement kle = new KthLargestElement();
int[] nums = { 3, 2, 1, 5, 6, 4 };
int k = 2;
System.out.println(kle.findKthLargest(nums, k));
}
}
```

**Performance**

The time complexity of the `findKthLargest`

method is O(n) because we iterate through the input array `nums`

once to calculate the frequency of each element. The space complexity is O(1) because we are using a fixed-size array `freq`

of size 20001 to store the frequency of elements, which does not depend on the size of the input array.

Thank you for reading!

Check out other DSA patterns **here**.

You can support me by **buying me a book****.**