# 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.


---

# 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://zedive.gitbook.io/project-l/part-1/basic_data_structure/array_and_string/unsorted-array/kth-largest-element.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.