Kth largest element

Summary

Given an unsorted array, find the k-th largest element. This problem involves using a priority queue or heap data structure to efficiently extract the k-th largest element.

Detailed Explanation

To solve this problem, we can use a max-heap to store the elements of the array. The idea is to insert all elements into the max-heap and then pop k-1 times to get the k-th largest element.

Here's a step-by-step breakdown of the solution:

Create an empty max-heap.
Iterate through the array, inserting each element into the max-heap.
Pop k-1 times from the max-heap to discard the k-1 smallest elements.
The top element in the max-heap is the k-th largest element.

The time complexity of this solution is O(n log n) due to the insertion and pop operations on the heap, where n is the size of the array. The space complexity is O(n) for storing the elements in the heap.

Here's an ASCII art diagram illustrating the steps:

  +---------------+
  |  Max-Heap     |
  +---------------+
           |
           v
  +---------------+
  |  Element 1    |
  |  Element 2    |
  |  ...          |
  |  Element n    |
  +---------------+

Optimized Solutions

Java

import java.util.PriorityQueue; public class KthLargestElement { public static int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b.compareTo(a)); for (int num : nums) { maxHeap.offer(num); } for (int i = 0; i < k - 1; i++) { maxHeap.poll(); } return maxHeap.peek(); } }