top of page
Search

Kth Largest Element in an Array

Writer's picture: Coding CampCoding Camp

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


19 views0 comments

Recent Posts

See All

Comments


bottom of page