# Kth Largest Element in an Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/kth-largest-element-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/kth-largest-element-in-an-array
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer), [Sorting](https://scaleengineer.com/algorithms/sorting), [Quickselect](https://scaleengineer.com/algorithms/quickselect)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [AMD](https://scaleengineer.com/companies/amd), [Accenture](https://scaleengineer.com/companies/accenture), [Avito](https://scaleengineer.com/companies/avito), [ByteDance](https://scaleengineer.com/companies/bytedance), [Deloitte](https://scaleengineer.com/companies/deloitte), [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Infosys](https://scaleengineer.com/companies/infosys), [Intuit](https://scaleengineer.com/companies/intuit), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [SAP](https://scaleengineer.com/companies/sap), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Spotify](https://scaleengineer.com/companies/spotify), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wipro](https://scaleengineer.com/companies/wipro), [Yandex](https://scaleengineer.com/companies/yandex), [eBay](https://scaleengineer.com/companies/ebay), [Coupang](https://scaleengineer.com/companies/coupang), [Salesforce](https://scaleengineer.com/companies/salesforce), [Turing](https://scaleengineer.com/companies/turing), [Pocket Gems](https://scaleengineer.com/companies/pocket-gems), [Verily](https://scaleengineer.com/companies/verily), [SIG](https://scaleengineer.com/companies/sig), [Guidewire](https://scaleengineer.com/companies/guidewire)
---
## Problem
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

**Constraints:**

* `1 <= k <= nums.length <= 105`
* `-104 <= nums[i] <= 104`

# Approaches
## Sorting Approach
Sort the array in descending order and return the kth element.
**Time:** O(n log n) where n is the length of the array due to sorting · **Space:** O(1) as sorting is done in-place in Java's implementation
**Pros:** Simple to implement; Easy to understand; Uses built-in sorting function
**Cons:** Not optimal time complexity; Modifies the original array; Sorts the entire array when we only need the kth largest element
### Explanation
This is the most straightforward approach where we sort the array in descending order and return the element at index k-1. While simple to implement, it's not the most efficient solution as it requires sorting the entire array.

```java
public int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k];
}
```

In this approach, we first sort the array using Java's built-in sorting algorithm (which uses a modified quicksort). After sorting, we return the element at index nums.length - k since the array is sorted in ascending order and we want the kth largest element.
### Algorithm
1. Sort the array using Arrays.sort()
2. Return the element at index nums.length - k

## Min Heap Approach
Maintain a min heap of size k to find the kth largest element.
**Time:** O(n log k) where n is the length of the array and k is the given value · **Space:** O(k) to store the heap
**Pros:** More efficient than sorting for large arrays; Doesn't modify the original array; Works well when k is small compared to n
**Cons:** Uses extra space; Not optimal when k is close to n; Requires a heap data structure
### Explanation
We can use a min heap to keep track of the k largest elements. We maintain a heap of size k, and for each element in the array, we add it to the heap if the heap size is less than k or if the element is larger than the smallest element in the heap.

```java
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();
}
```

In this approach, we use a PriorityQueue (which is implemented as a min heap in Java). We keep adding elements to the heap, and whenever the size exceeds k, we remove the smallest element. This way, after processing all elements, the heap contains the k largest elements with the kth largest at the top.
### Algorithm
1. Create a min heap (PriorityQueue)
2. Iterate through the array
3. Add each element to the heap
4. If heap size exceeds k, remove the smallest element
5. Return the top element of the heap

## QuickSelect Approach
Use the QuickSelect algorithm (based on QuickSort partition) to find the kth largest element.
**Time:** Average case O(n), Worst case O(n²) where n is the length of the array · **Space:** O(1) as it's done in-place
**Pros:** Optimal average-case time complexity; No extra space needed; Doesn't need to sort the entire array; Best solution when we only need to find one element
**Cons:** Modifies the original array; Worst case time complexity is O(n²); Not stable (doesn't preserve relative order of equal elements)
### Explanation
The QuickSelect algorithm is an optimized approach that uses the partition scheme of QuickSort. Instead of recursing on both sides like in QuickSort, we only recurse on the side that contains the kth largest element.

```java
public int findKthLargest(int[] nums, int k) {
    return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}

private int quickSelect(int[] nums, int left, int right, int k) {
    if (left == right) return nums[left];
    
    int pivotIndex = partition(nums, left, right);
    
    if (pivotIndex == k) return nums[k];
    else if (pivotIndex < k) return quickSelect(nums, pivotIndex + 1, right, k);
    else return quickSelect(nums, left, pivotIndex - 1, k);
}

private int partition(int[] nums, int left, int right) {
    int pivot = nums[right];
    int i = left;
    
    for (int j = left; j < right; j++) {
        if (nums[j] <= pivot) {
            swap(nums, i, j);
            i++;
        }
    }
    swap(nums, i, right);
    return i;
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
```

This approach uses the partition scheme to place elements smaller than the pivot on the left and larger elements on the right. We only need to recurse on the side that contains our target index.
### Algorithm
1. Use QuickSelect algorithm with partition scheme
2. Choose a pivot element
3. Partition array around pivot
4. If pivot index is target index, return element
5. Otherwise, recurse on appropriate half
6. Repeat until kth largest is found

# Solutions
### Java

```java
class Solution {
public
  int findKthLargest(int[] nums, int k) {
    int n = nums.length;
    return quickSort(nums, 0, n - 1, n - k);
  }
private
  int quickSort(int[] nums, int left, int right, int k) {
    if (left == right) {
      return nums[left];
    }
    int i = left - 1, j = right + 1;
    int x = nums[(left + right) >>> 1];
    while (i < j) {
      while (nums[++i] < x)
        ;
      while (nums[--j] > x)
        ;
      if (i < j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
      }
    }
    if (j < k) {
      return quickSort(nums, j + 1, right, k);
    }
    return quickSort(nums, left, j, k);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findKthLargest(vector<int> &nums, int k) {
    int n = nums.size();
    return quickSort(nums, 0, n - 1, n - k);
  }
  int quickSort(vector<int> &nums, int left, int right, int k) {
    if (left == right)
      return nums[left];
    int i = left - 1, j = right + 1;
    int x = nums[left + right >> 1];
    while (i < j) {
      while (nums[++i] < x)
        ;
      while (nums[--j] > x)
        ;
      if (i < j)
        swap(nums[i], nums[j]);
    }
    return j < k ? quickSort(nums, j + 1, right, k)
                 : quickSort(nums, left, j, k);
  }
};

```

### Python

```python
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int: lo, hi = 0, len(nums) - 1 while lo <= hi: pos = self . partition(nums, lo, hi) if pos == k - 1:  # pos starting from 0, so -1 return nums [ pos ] # partially sorted, desc elif pos > k - 1 : hi = pos - 1 else : # pos < k - 1 lo = pos + 1 return - 1 # or raise exception def partition ( self , nums : List [ int ], lo : int , hi : int ) -> int : pivot , l , r = nums [ lo ], lo + 1 , hi while l <= r : if nums [ l ] < pivot and nums [ r ] > pivot : # larger num at left of pivot, easier to count for k-th lagest nums [ l ], nums [ r ] = nums [ r ], nums [ l ] l += 1 r -= 1 if nums [ l ] >= pivot : l += 1 if nums [ r ] <= pivot : r -= 1 # use nums[l] will lead to infinate looping nums [ lo ], nums [ r ] = nums [ r ], nums [ lo ] # possible there is duplicated num, but will be covered here return r ############## class Solution : def findKthLargest ( self , nums : List [ int ], k : int ) -> int : def quick_sort ( left , right , k ): if left == right : return nums [ left ] i , j = left - 1 , right + 1 x = nums [( left + right ) >> 1 ] while i < j : while 1 : i += 1 if nums [ i ] >= x : break while 1 : j -= 1 if nums [ j ] <= x : break if i < j : nums [ i ], nums [ j ] = nums [ j ], nums [ i ] if j < k : return quick_sort ( j + 1 , right , k ) return quick_sort ( left , j , k ) n = len ( nums ) return quick_sort ( 0 , n - 1 , n - k ) ############ class Solution : def findKthLargest ( self , nums : List [ int ], k : int ) -> int : def quick_sort ( left , right , k ): if left == right : return nums [ left ] i , j = left - 1 , right + 1 x = nums [( left + right ) >> 1 ] while i < j : while 1 : i += 1 if nums [ i ] >= x : break while 1 : j -= 1 if nums [ j ] <= x : break if i < j : nums [ i ], nums [ j ] = nums [ j ], nums [ i ] if j < k : return quick_sort ( j + 1 , right , k ) return quick_sort ( left , j , k ) n = len ( nums ) return quick_sort ( 0 , n - 1 , n - k )

```