Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

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

Example 2:

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

Note: You may assume k is always valid, 1 ≤ k ≤ array's length.

Solution:

1. Sorting:

class Solution {public int findKthLargest(int[] nums, int k) 
  {       
        Arrays.sort(nums);
        return nums[nums.length -k];
    }

2. Heap:

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

3. Partitioning:

class Solution {
    public int findKthLargest(int[] nums, int k) {
    int n = nums.length;
    int left = 0;
    int right = n - 1;

    Random rand = new Random(0);

    while (left <= right) {
      int choosenIndex = rand.nextInt(right - left + 1) + left;

      int finalIndex = partition(nums, left, right, choosenIndex);
      if (finalIndex == n - k) {
        return nums[finalIndex];
      } else if (finalIndex > n - k) {
        right = finalIndex - 1;
      } else {
        left = finalIndex + 1;
      }
    }

    return -1;
  }

  private int partition(int[] arr, int left, int right, int pivotIndex) {
    int pivotValue = arr[pivotIndex];
    int lesserIndex = left;
    swap(arr, pivotIndex, right);

    for (int i = left; i < right; i++) {
      if (arr[i] < pivotValue) {
        swap(arr, i, lesserIndex);
        lesserIndex++;
      }
    }

    swap(arr, right, lesserIndex);

    return lesserIndex;
  }

  private void swap(int[] arr, int first, int second) {
    int temp = arr[first];
    arr[first] = arr[second];
    arr[second] = temp;
  }
}