> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/array_and_string/unsorted-array/kth-largest-element.md).

# Kth Largest Element

## Question ([LC.215](https://leetcode.com/problems/kth-largest-element-in-an-array/))

> Given an unsorted array, find the kth largest element.

## Example

```
([3,2,1,5,6,4], 2) => 5
```

## Brute Force

Sort the input array. Then return the n-k smallest element.

```java
Arrays.sort(nums);
return nums[nums.length - k];
```

## Priority Queue

We need to somehow structure this unstructured data. Maintain a min heap of size k. Poll as we go.

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

Time O(nlogk) Space O(k)

## Quick Select

A true linear time algorithm doesn't exist for an unsorted array. But we can randomly pick a pivot and hope that it will structure some parts of the data. We can use the partition step from quick sort to help us to do that.

```java
public int findKthLargest(int[] nums, int k) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    if (k <= 0 || k > nums.length) {
        return -1;
    }
    return quickSelect(nums, nums.length - k + 1, 0, nums.length - 1);
}

// Quickly select the kth _smallest_ element
private int quickSelect(int[] arr, int k, int start, int end) {
    // base case
    if (start == end) {
        return arr[start];
    }
    // divide
    int pivotPos = partition(arr, start, end);
    // conquer
    if (k - 1 == pivotPos) {
        return arr[pivotPos];
    } else if (k - 1 < pivotPos) {
        return quickSelect(arr, k, start, pivotPos - 1);
    } else {
        return quickSelect(arr, k, pivotPos + 1, end);
    }
}

private int partition(int[] arr, int start, int end) {
    int pivot = arr[start];
    int i = start + 1, j = end;
    while (i <= j) {
        // swap after both pointers invalidate the condition
        while (i <= j && arr[i] < pivot) i++;
        while (i <= j && arr[j] >= pivot) j--;
        if (i <= j) {
            swap(arr, i, j);
            i++;
            j--;
        }
    }
    // swap the pivot with the last element smaller than it
    swap(arr, j, start);
    return j;
}
```

Be mindful on the post condition after partition. `j` becomes the end the smaller section and `i` becomes the start of the larger section.

Time O(n) on average because the geometric sum proves T(n) = O(n) + T(n/2) = O(n).

## Median Variant ([LI.80](http://www.lintcode.com/en/problem/median/))

`k=length/2` if even `k=length/2 + 1` if odd

```java
public int median(int[] nums) {
    int length = nums.length;
    if (length % 2 == 1)
        return findKthSmallest(nums, length / 2 + 1);
    else
        return findKthSmallest(nums, length / 2);
}

private int findKthSmallest(int[] arr, int k) {
    return quickSelect(arr, k, 0, arr.length - 1);
}
```

## Mailbox Variant ([EPI](https://stackoverflow.com/questions/44725690/algorithm-to-place-a-mailbox-to-minimize-the-total-distance-that-the-residents-t))

> Given an unordered list of building objects, find the best place a mailbox to minimize the total distance.