Kth Largest Element In An Array

                                            
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq;
        
        for(int num : nums) {
            pq.push(num);
            if(pq.size() > k) {
                pq.pop();
            }
        }
        
        return pq.top();
    }
};

                                            
class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int num : nums) {
            pq.offer(num);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        
        return pq.peek();
    }
}

                                            
import heapq

class Solution(object):
    def findKthLargest(self, nums, k):
        return heapq.nlargest(k, nums)[-1]

                                            
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int *)b - *(int *)a);
}

int findKthLargest(int* nums, int numsSize, int k) {
    qsort(nums, numsSize, sizeof(int), compare);
    return nums[k-1];
}

                                            
public class Solution {
    public int FindKthLargest(int[] nums, int k) {
        Array.Sort(nums);
        return nums[nums.Length - k];
    }
}

                                            
var findKthLargest = function(nums, k) {
    return nums.sort((a, b) => b - a)[k - 1];
};

                                            
function findKthLargest(nums: number[], k: number): number {
    const sortedNums = nums.sort((a, b) => b - a);
    return sortedNums[k - 1];
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer
     */
    function findKthLargest($nums, $k) {
        $n = count($nums);
        $heap = new SplMaxHeap();
        
        foreach ($nums as $num) {
            $heap->insert($num);
        }
        
        $result = 0;
        for ($i = 0; $i < $k; $i++) {
            $result = $heap->extract();
        }
        
        return $result;
    }
}

                                            
class Solution {
    func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
        var nums = nums
        return quickSelect(&nums, 0, nums.count - 1, k)
    }
    
    func quickSelect(_ nums: inout [Int], _ left: Int, _ right: Int, _ k: Int) -> Int {
        let pivotIndex = partition(&nums, left, right)
        if pivotIndex == k - 1 {
            return nums[pivotIndex]
        } else if pivotIndex < k - 1 {
            return quickSelect(&nums, pivotIndex + 1, right, k)
        } else {
            return quickSelect(&nums, left, pivotIndex - 1, k)
        }
    }
    
    func partition(_ nums: inout [Int], _ left: Int, _ right: Int) -> Int {
        let pivot = nums[right]
        var i = left
        for j in left..<right {
            if nums[j] >= pivot {
                nums.swapAt(i, j)
                i += 1
            }
        }
        nums.swapAt(i, right)
        return i
    }
}

                                            
class Solution {
    fun findKthLargest(nums: IntArray, k: Int): Int {
        val pq = PriorityQueue<Int>()
        
        for (num in nums) {
            pq.offer(num)
            if (pq.size > k) {
                pq.poll()
            }
        }
        
        return pq.peek()
    }
}

                                            
import 'dart:math';

class Solution {
  int findKthLargest(List<int> nums, int k) {
    nums.sort((a, b) => b - a);
    return nums[k - 1];
  }
}

                                            
# @param {Integer[]} nums
# @param {Integer} k
# @return {Integer}
def find_kth_largest(nums, k)
    nums.sort[-k]
end

                                            
(define/contract (find-kth-largest nums k)
  (-> (listof exact-integer?) exact-integer? exact-integer?)
  
  (define sorted-nums (sort nums >))
  (list-ref sorted-nums (sub1 k))
)

                                            
-spec find_kth_largest(Nums :: [integer()], K :: integer()) -> integer().
find_kth_largest(Nums, K) ->
    lists:max(lists:sublist(lists:sort(Nums), length(Nums) - K + 1)).

To solve this coding challenge, where we need to find the kth largest element in an unsorted array without sorting the entire array, we can make use of data structures that efficiently help us keep track of the largest elements in the array.

Explanation

The challenge is to find the kth largest element in an array without sorting the entire array. Sorting the array would take O(n log n) time complexity, but we need a more efficient solution. We can use a min-heap to do this more efficiently. Min-heaps are a type of binary heap where the root node is the smallest element. They have efficient insert and delete operations which are O(log k) when the heap contains k elements. By maintaining a min-heap of size k, we ensure that we can always get the kth largest element in the heap's root. Here’s how the approach works:

Initialize an empty min-heap.
Iterate over each element in the array, adding elements to the heap.
If the size of the heap exceeds k, remove the smallest element (the root).
After processing all elements, the root of the heap will be the kth largest element.

This approach ensures that we are only maintaining k elements in the heap at any time, leading to a time complexity of O(n log k), which is a significant improvement over O(n log n) for sorting.

Detailed Steps in Pseudocode

Create a min-heap to store the kth largest elements as we iterate through the array.
Iterate through each element in the array:

Add the current element to the heap.
If the size of the heap exceeds k, remove the smallest element from the heap.

After iterating through all elements, the root of the heap (the smallest element in the heap) will be the kth largest element in the array.
Return the root of the min-heap as the kth largest element.

Pseudocode

                                            
# Initialize an empty data structure to act as the heap.
minHeap = []

# Iterate over all elements in the given array nums.
for element in nums:
    # Add the current element to the min-heap.
    add element to minHeap
    
    # If the size of the min-heap exceeds k, remove the smallest element (heap's root).
    if size of minHeap > k:
        remove the smallest element (root of the heap) from minHeap

# After processing all elements, the heap's root is the kth largest element.
kthLargestElement = root of minHeap

# Return the kth largest element.
return kthLargestElement

In the pseudocode above:

The
minHeap

is used to maintain the k largest elements encountered so far.
The operation to "add element to minHeap" ensures that the element is added while maintaining the heap property.
The condition
if size of minHeap > k

ensures that only the k largest elements are retained in the heap.
After processing all elements, the root of the
minHeap

(smallest element in the heap) will be the kth largest element in the array.

By adhering to this approach, we ensure a more efficient solution with a time complexity of O(n log k), which is much better than O(n log n) required for full sorting.