Sponsored
Sponsored
By using a Min-Heap, we can efficiently keep track of the k largest elements. Maintain a heap of size k, and for each element in the array, decide whether to add it to the heap. If you add an element to the heap when it is full, remove the minimum element to maintain the size of the heap as k. At the end, the root of the heap will be the kth largest element.
Time Complexity: O(n log n), where n is the size of the array, because of the sorting operation.
Space Complexity: O(1), as we are modifying the input array in-place.
1using System;
2using System.Collections.Generic;
3
4class KthLargestElement {
5 static int FindKthLargest(int[] nums, int k) {
6 SortedSet<(int, int)> minHeap = new SortedSet<(int, int)>();
7 foreach (int num in nums) {
8 minHeap.Add((num, num));
9 if (minHeap.Count > k) {
10 minHeap.Remove(minHeap.Min);
11 }
12 }
13 return minHeap.Min.Item1;
14 }
15
16 static void Main() {
17 int[] nums = {3,2,1,5,6,4};
18 int k = 2;
19 Console.WriteLine(FindKthLargest(nums, k));
20 }
21}Using C# SortedSet to simulate a min-heap by storing elements as tuples of `(num, num)` to handle duplicates. Maintain a size of k elements by removing the smallest element once the set exceeds k elements. The smallest element remaining is the kth largest.
Quickselect is an efficient selection algorithm to find the kth smallest element in an unordered list. The algorithm is related to the quicksort sorting algorithm. It works by partitioning the data, similar to the partitioning step of quicksort, and is based on the idea of reducing the problem size through partitioning.
Average-case Time Complexity: O(n), but worst-case O(n²).
Space Complexity: O(1) for iterative solution, O(log n) for recursive calls due to stack depth.
1#
The quickSelect function recursively partitions the array around pivot elements. The function partition ensures the pivot is in its sorted position with all larger numbers left and smaller numbers right. If the pivot's index equals k, the pivot is the kth largest element. We adjust to 0-based index during each call.