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

Kth Largest Element
Wikipedia: Animated visualization of the quickselect algorithm.

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;
}
}

Thank you for reading. Happy Learning! :)

Originally published at https://vishwajeet.blog.

Java and ADF developer for 12+ years. Love Java , WordPress , SQL, PLSQL and related technologies. Open source enthusiast.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store