To see the question, click here.

Naive Approach

To find the kth largest element, we can first sort the array and then return the nums.length - k th element.

// TC: O(nlogn)
// SC: O(1)

import java.util.Arrays;

class KthLargestElement {

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

    public static void main(String args[]) {
        KthLargestElement kle = new KthLargestElement();
        int[] nums = { 3, 2, 1, 5, 6, 4 };
        int k = 2;
        System.out.println(kle.findKthLargest(nums, k));
    }
}

Performance

The time complexity of the findKthLargest method is O(nlogn) because it involves sorting the input array nums using the Arrays.sort() method, which has a time complexity of O(nlogn). The space complexity is O(1) because the sorting is done in place and does not require any additional space proportional to the input size.

Refined Approach

To find the kth largest element, we will utilize a PriorityQueue which in turn is a min-heap. We offer each element in the array to the min-heap, and after the offering, we will check if the size of the heap exceeds k. If it does, the smallest element (which is at the top of the min-heap) is removed to ensure that the heap always contains the largest k elements seen so far.

// TC: O(nlogk)
// SC: O(k)

import java.util.PriorityQueue;

class KthLargestElement {

    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.offer(num);

            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        return minHeap.peek();
    }

    public static void main(String args[]) {
        KthLargestElement kle = new KthLargestElement();
        int[] nums = { 3, 2, 1, 5, 6, 4 };
        int k = 2;
        System.out.println(kle.findKthLargest(nums, k));
    }
}

Performance

The time complexity of the findKthLargest method is O(nlogk). This is because we are iterating through each element in the input array and performing operations on a priority queue of size k, which has a time complexity of O(logk) to insert and remove elements. The space complexity of the findKthLargest method is O(k). This is because we use a priority queue of size k to store the k largest elements in the input array.

Efficient Approach 1

The concept involves a "quick select" technique similar to the "quick sort" algorithm. It's important to note that the Kth largest element in an array is equivalent to the (N – K)th smallest element. Initially, we select a "pivot" element, akin to the quick sort approach. This is achieved through a specific procedure called "partitioning." During this procedure, we compare each element with the pivot. Elements smaller than the pivot are shifted to the left, while larger ones are moved to the right. Consequently, the array is divided into two segments. We can disregard one segment and concentrate on locating the (N – K)th element in the remaining segment.

// TC: O(n)
// SC: O(1)

class KthLargestElement {
    public int findKthLargest(int[] numbers, int k) {
        k = numbers.length - k; // Convert k to index of k-th largest element
        int low = 0;
        int high = numbers.length - 1;

        while (low < high) {
            int partitionIndex = partition(numbers, low, high);
            if (partitionIndex < k) {
                low = partitionIndex + 1;
            } else if (partitionIndex > k) {
                high = partitionIndex - 1;
            } else {
                break;
            }
        }
        return numbers[k];
    }

    private int partition(int[] numbers, int low, int high) {
        int pivot = numbers[low];
        int i = low;
        int j = high + 1;

        while (true) {
            // Move i to the right until finding a number greater than or equal to the pivot
            while (i < high && numbers[++i] < pivot);
            // Move j to the left until finding a number less than or equal to the pivot
            while (j > low && numbers[low] < numbers[--j]);
            if (i >= j) {
                break;
            }
            swap(numbers, i, j);
        }
        swap(numbers, low, j); // Place pivot in its correct position
        return j;
    }

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

    public static void main(String args[]) {
        KthLargestElement kle = new KthLargestElement();
        int[] nums = { 3, 2, 1, 5, 6, 4 };
        int k = 2;
        System.out.println(kle.findKthLargest(nums, k));
    }
}

Performance

The time complexity of the findKthLargest method is O(n) on average. This is because the partition method is called on each iteration of the while loop, which takes O(n) time in the worst-case scenario. The average time complexity is O(n) because the partitioning process divides the array into two roughly equal parts. The space complexity of the algorithm is O(1) because it does not use any extra space that grows with the input size. The algorithm sorts the input array in place without using any additional data structures.

Efficient Approach 2

The range for the elements inside the array is -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup> . If the nums[i] started from 0, we could have initialized an array of size 10⁴+1, traversed it, and incremented the count in the index based on the element, i.e., if the element is 2, we will increment the value in index 2. We could have found the kth largest element by traversing from the back. Since we cannot have negative indices, we will create an array of size 2x10⁴+1 so that the first 10⁴ blocks are for negative numbers and the remaining are for non-negative numbers. This method is not recommended as this can lead to significant memory usage, especially if the range of values is large.

// TC: O(n)
// SC: O(1)

class KthLargestElement {
    public int findKthLargest(int[] nums, int k) {
        int[] freq = new int[20001];
        for (int num : nums)
            freq[num + 10000]++;
        for (int i = 20000; i >= 0; i--) {
            k -= freq[i];
            if (k <= 0)
                return i - 10000;
        }
        return -1;
    }

    public static void main(String args[]) {
        KthLargestElement kle = new KthLargestElement();
        int[] nums = { 3, 2, 1, 5, 6, 4 };
        int k = 2;
        System.out.println(kle.findKthLargest(nums, k));
    }
}

Performance

The time complexity of the findKthLargest method is O(n) because we iterate through the input array nums once to calculate the frequency of each element. The space complexity is O(1) because we are using a fixed-size array freq of size 20001 to store the frequency of elements, which does not depend on the size of the input array.

Thank you for reading!

Check out other DSA patterns here.

You can support me by buying me a book.