# 215. Kth Largest Element in an Array

![](/files/-Mh2VvGk1zMkf_MeFSpe)

## 1. Sort

time: O(nlogn)

space: O(1)

## 2. heap

#### main a min heap, size is k, pop min value

so at last last, we pop, it's k th largest (smallest

time: O(nlogk), add to heap is O(logk), do n times

space: O(k)

```java
class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.poll();
    }
}
```

## Quickselect

time: O(n), worst O(n^2)

space: O(1), in place sort

```java
class Solution {
    public int findKthLargest(int[] nums, int k) {
        return findKthSmallest(nums, 0, nums.length - 1, nums.length - k); // find Kth Largest is find (n-k) Kth smallest
    }
    
    private int findKthSmallest(int[] nums, int left, int right, int ksmallest) {
        if (left == right) return nums[left]; // only one element
        
        Random random = new Random();
        int randomPivot = left + random.nextInt(right - left);
        int pivot = partition(nums, left, right, randomPivot);
        
        if (ksmallest == pivot) { // bingo!
            return nums[ksmallest];
        } else if (ksmallest < pivot) { // find left side
            return findKthSmallest(nums, left, pivot - 1, ksmallest);
                
        } else { // find right side
            return findKthSmallest(nums, pivot + 1, right, ksmallest);
        }
    }
    
    private int partition(int[] nums, int left, int right, int pivot) {
        int pivotVal = nums[pivot];
        swap(nums, pivot, right);
        int storedIndex = left;
        
        for (int i = left; i < right; i++) {
            if (nums[i] < pivotVal) {
                swap(nums, storedIndex, i);
                storedIndex++;
            }
        }
        swap(nums, storedIndex, right);
        return storedIndex;
    }
    private void swap(int nums[], int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
```

## faster version of quickselect

```java
class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, k);
    }
    private int quickSelect(int[] nums, int start, int end, int k) {
        if (start >= end) {
            return nums[start];
        }
        
        // partition
        int pivotValue = nums[(start+end)/2];
        int i = start;
        int j = end;
        while (i <= j) {
            while (i <= j && nums[i] > pivotValue) {
                i++;
            }
            while (i <= j && nums[j] < pivotValue) {
                j--;
            }
            if (i <= j) {
                swap(nums, i, j);
                i++;
                j--;
            }
        }
        
        if (start + k - 1 <= j) {
            return quickSelect(nums, start, j, k);
        }
        if (start + k - 1 >= i) {
            return quickSelect(nums, i, end, k - (i-start));
        }
        return nums[j+1];
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/kth/215.-kth-largest-element-in-an-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.