Kth Largest Element in an Array

Problem

Given an integer array nums and an integer k, return the k<sup>th</sup> largest element in the array. Note that it is the k<sup>th</sup> largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting? (link)

Example 1:

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

Example 2:

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

Constraints:

• 1 <= k <= nums.length <= 10^5

• -10^4 <= nums[i] <= 10^4

Solution

Brute Force Approach (Quick Sort - Partition Logic)

We use the core part of the quicksort algorithm, which is the partition index logic. In quicksort, the partition function provides the index where the pivot element is placed in the correct position in the given array if all the elements are sorted. We compare the partition index with the required index, which is the kth largest element (n-k) in the sorted array. We keep calling the partition function until we get the index n-k.

Time Complexity: O(n^2)

Space Complexity: O(1)

The maximum number of times the for loop can run is n because we get n indices that have the correct elements. The partition function can take a maximum of O(n) time.

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

        for(int i=0;i<n;i++){
            int partitionIndex = partition(nums,low,high);

            if(partitionIndex==n-k) return nums[partitionIndex];

            if(partitionIndex<n-k) low = partitionIndex + 1;
            else high = partitionIndex - 1; 
        }
        return -1;
    }

    private int partition(int[] nums, int low, int high){
        int leftPtr = low;
        int rightPtr = high;
        int pivot = low;

        while(leftPtr<rightPtr){
            while(leftPtr<=high && nums[pivot]>=nums[leftPtr]) leftPtr+=1; 

            while(rightPtr>=low && nums[pivot]<nums[rightPtr]) rightPtr-=1;

            if(leftPtr<rightPtr) swap(nums,leftPtr, rightPtr);
        }
        swap(nums,pivot,rightPtr);
        return rightPtr;
    }

    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Better Approach (Sort)

Directly sort the array and return the index of n-k, which is the kth largest element, where n is length of the array

Time - O(nlogn)

Space - O(1)

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

Optimal Approach (Priority Queue)

In this approach, we use extra space to iterate through all the elements and store them in a priority queue. A priority queue is essentially a heap that stores the minimum element at the root for a min heap and the maximum element at the root for a max heap. We use a max heap priority queue, which stores the maximum element at the root.

We then pop the root of the max heap priority queue ( k-1 ) times and return the root of the priority queue. Each time we pop the root, it is replaced by the next maximum element available in the queue. This method effectively gives us the kth largest element.

Time - O(n) + O(klogn)

Space - O(n)

• The size of heap binary tree is log(n)

• Each poll operation takes log(n)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((Integer a, Integer b)-> b-a);

        for(int element : nums){
            pq.add(element);
        }

        for(int i = 1; i<k ; i++){
            pq.poll();
        }
        return pq.peek();
    }
}