# Solution For Kth Largest Element In An Array

Problem:

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

Solution:

This problem can be solved in multiple ways, some of the most common ones are:

1. Sorting: Sort the array in descending order and return the kth element.

2. Min Heap: Create a min heap of size k, iterate through the array and add each element to the heap. If the heap size exceeds k, remove the smallest element from the heap. The kth largest element will be the root of the heap.

3. Quick Select Algorithm: This is a modified version of Quick Sort algorithm where we only partition those elements that we care about i.e. the (n-k)th to n-1th elements where n is the length of the array. The pivot element after each partition gives us an idea about the position of the kth largest element. If the pivot element is at index n-k, we have found our answer.

In this solution, we will use the Quick Select Algorithm to solve this problem.

Algorithm:

1. Define a function `partition` that takes an array, a start index and an end index as input and returns the pivot index after partitioning the array.

2. Set the pivot index to the start index and the pivot value to the last element of the array.

3. Initialize the left index to the start index and the right index to the end index – 1.
4. Loop until the left index is less than or equal to the right index:
• If the value at index left is less than or equal to the pivot value, increment left.
• If the value at index right is greater than or equal to the pivot value, decrement right.
• If the value at index left is greater than the pivot value and the value at index right is less than the pivot value, swap the values at indexes left and right.
5. Swap the pivot value with the value at index left.
6. Return the left index.

7. Define a function `quickSelect` that takes an array, a start index, an end index, and a k value as input and returns the kth largest element in the array.

8. If the start index is equal to the end index, return the value at index start.

9. Call the `partition` function with the array, start index, and end index, and store the result in a variable `pivotIndex`.
10. If the pivotIndex is equal to n – k, return the value at index pivotIndex.
11. If the pivotIndex is less than n – k, call the `quickSelect` function recursively on the right half of the array with the start index set to pivotIndex + 1.
12. If the pivotIndex is greater than n – k, call the `quickSelect` function recursively on the left half of the array with the end index set to pivotIndex – 1.

13. Call the `quickSelect` function with the input array, start index set to 0, end index set to the length of the array – 1, and k value set to the input k.

14. Return the result of the `quickSelect` function.

Time Complexity:

On average, the time complexity of this algorithm is O(n) where n is the length of the input array. However, in worst-case scenarios, the time complexity can be O(n^2) when the array is sorted in ascending or descending order.

Space Complexity:

The space complexity of this algorithm is O(1) as we are not using any extra data structures.

Code:

“`
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:

``````    def partition(nums, start, end):
pivotIndex = start
pivotValue = nums[end]
leftIndex = start
rightIndex = end - 1

while leftIndex <= rightIndex:
if nums[leftIndex] <= pivotValue:
leftIndex += 1
elif nums[rightIndex] >= pivotValue:
rightIndex -= 1
elif nums[leftIndex] > pivotValue and nums[rightIndex] < pivotValue:
nums[leftIndex], nums[rightIndex] = nums[rightIndex], nums[leftIndex]
leftIndex += 1
rightIndex -= 1

nums[leftIndex], nums[end] = nums[end], nums[leftIndex]

return leftIndex

def quickSelect(nums, start, end, k):
if start == end:
return nums[start]

pivotIndex = partition(nums, start, end)

if pivotIndex == len(nums) - k:
return nums[pivotIndex]
elif pivotIndex < len(nums) - k:
return quickSelect(nums, pivotIndex + 1, end, k)
else:
return quickSelect(nums, start, pivotIndex - 1, k)

return quickSelect(nums, 0, len(nums) - 1, k)
``````

“`

## Step by Step Implementation For Kth Largest Element In An Array

```public int findKthLargest(int[] nums, int k) {

// Sort the given array
Arrays.sort(nums);

// Return the k'th element in
// the sorted array
return nums[nums.length - k];
}```
```def findKthLargest(nums, k):

# sort the list in descending order
nums.sort(reverse = True)

# return the kth element in the sorted list
return nums[k-1]```
```/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
// sort the array in reverse order
nums.sort((a, b) => b - a);

// return the kth element in the array
return nums[k - 1];
};```
```int findKthLargest(vector& nums, int k) {

// create a min heap
priority_queue, greater> minHeap;

// insert all elements into the min heap
for (int i = 0; i < nums.size(); i++) {
minHeap.push(nums[i]);
}

// extract the top k elements from the min heap
for (int i = 0; i < k - 1; i++) {
minHeap.pop();
}

// the top element of the min heap is the kth largest element
return minHeap.top();
}```
```public int FindKthLargest(int[] nums, int k)
{
// Sort the array in descending order
Array.Sort(nums);

// Return the kth element in the array
return nums[k - 1];
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]