> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/priority-queue/kth-largest-element-in-an-array.md).

# Kth Largest Element in an Array

Find the **k**th 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.<br>

```java
class Solution {
    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    public int findKthLargest(int[] A, int k) {
        k = A.length - k; // convert to index of k largest
        int left = 0, right = A.length - 1;
        while (left <= right) {
            // Choosing left index as pivot element
            int i = left;
            for (int j = left + 1; j <= right; j++)
                if (A[j] < A[left]) {
                    i++;
                    swap(A, j, i);
                }
            // 'i' will be the head of list of element < pivot
            swap(A, left, i);

            if (k < i)
                right = i - 1;
            else if (k > i)
                left = i + 1;
            else
                return A[i];
        }
        return -1; // k is invalid
    }
}
```