# LeetCode: Kth Largest Element In An Array

# Problem: Kth Largest Element In An Array

**Q**. Given an integer array “**nums”** and an integer “**k”**, return the “**kth**” largest element in the array.

**Note**: It is the kth largest element in the sorted order, not the kth distinct element.

# Examples

**Input**: nums = [3,2,1,5,6,4], k = 2**Output**: 5

**Input**: nums = [3,2,3,1,2,4,5,5,6], k = 4**Output**: 4

# Algorithm: Sorting

The naive solution is to sort the input array first and then return the kth element from the end.

- Time complexity: O(n log n)
- Space complexity: O(1)

`class Solution {`

public int findKthLargest(int[] nums, int k) {

if (nums.length == 0 || k > nums.length) {

return -1;

}

Arrays.sort(nums);

return nums[nums.length - k];

}

}

# Algorithm: Heap

The idea is to initialize a heap (min-heap) “the smallest element first”, and add all elements from the array into this heap one by one keeping the size of the heap always less or equal to k. That will result in a heap containing k largest elements of the array.

The head of this heap is the answer, i.e. the kth largest element of the array.

The time complexity of adding an element in a heap of size k is O(log k), and we add **n** elements, thus O(n log k) is the time complexity for this algorithm.

This algorithm improves time complexity, but one pays with O(k) space complexity.

- Time complexity: O(n log k)
- Space complexity: O(k)

`class Solution {`

public int findKthLargest(int[] nums, int k) {

if (nums.length == 0 || k > nums.length) {

return -1;

}

PriorityQueue heap = new PriorityQueue();

for (int n : nums) {

heap.add(n);

if (heap.size() > k) {

heap.poll();

}

}

return heap.poll();

}

}

# Algorithm: Quickselect

Quickselect is a selection algorithm to find the kth smallest element in an unordered list. It is related to the quicksort sorting algorithm. Like quicksort, it was developed by Tony Hoare, and thus is also known as Hoare’s selection algorithm. Like quicksort, it is efficient in practice and has good average-case performance, but has poor worst-case performance.

Notice here that the kth largest element is the same as (n - k) smallest element, hence one could implement the kth smallest algorithm for this problem.

Quickselect uses the same overall approach as quicksort, choosing one element as a pivot and partitioning the data in two based on the pivot, accordingly as less than or greater than the pivot. However, instead of recursing into both sides, as in quicksort, quickselect only recurses into one side — the side with the element it is searching for. This reduces the average complexity from O(n log n) to O(n), with a worst-case of O(n2).

**Steps**:

- Choose a random pivot.
- Use a partitioning algorithm to place the pivot into its perfect position pos in the sorted array, move smaller elements to the left of pivot, and larger or equal ones - to the right.
- Compare pos and n - k to choose the side of the array to proceed recursively.

Notice that this algorithm works well even for arrays with duplicates.

- Time complexity: O(n) in the best/average case, О(n^2) in the worst case
- Space complexity: O(1)

class Solution { public int findKthLargest(int[] nums, int k) {

if (nums.length == 0 || k > nums.length) {

return -1;

}

return quickSelect(nums, 0, nums.length - 1, nums.length - k);

} private int quickSelect(int[] array, int left, int right, int kthSmallestElementIndex) {

if (left == right) {

return array[left];

}

Random r = new Random();

int pivotIndex = left + r.nextInt(right - left);

pivotIndex = partition(array, left, right, pivotIndex);

if (kthSmallestElementIndex == pivotIndex) {

return array[kthSmallestElementIndex];

} else if (kthSmallestElementIndex < pivotIndex) { // go left

return quickSelect(array, left, pivotIndex - 1, kthSmallestElementIndex);

} else { // go right

return quickSelect(array, pivotIndex + 1, right, kthSmallestElementIndex);

}

} private int partition(int[] array, int left, int right, int pivotIndex) {

int pivotNumber = array[pivotIndex];

swap(array, pivotIndex, right);

int i = left;

while (i <= right) {

if (array[i] < pivotNumber) {

swap(array, left, i);

left++;

}

i++;

}

swap(array, left, right);

return left;

} private void swap(int[] array, int i, int j) {

int temp = array[i];

array[i] = array[j];

array[j] = temp;

}

}

# References

# Explore

# Subscribe

- Click here to subscribe to the “By Vishwajeet” blog and receive notifications of new posts by email.

*Thank you for reading. Happy Learning! :)*

*Originally published at **https://vishwajeet.blog**.*