Kth Largest Element in an Array

class Solution {
public:
    int findKthLargestElement(vector<int>& elements, int k) {
        int smallest = INT_MAX;
        int largest = INT_MIN;
        
        for (int value: elements) {
            smallest = min(smallest, value);
            largest = max(largest, value);
        }
        
        vector<int> freq(largest - smallest + 1);
        for (int value: elements) {
            freq[value - smallest]++;
        }
        
        int counter = k;
        for (int i = freq.size() - 1; i >= 0; i--) {
            counter -= freq[i];
            if (counter <= 0) {
                return i + smallest;
            }
        }
        
        return -1;
    }
};

This solution demonstrates how to find the Kth largest element in an array using C++. The approach involves the following steps:

1. Initialize two variables, smallest and largest, to track the minimum and maximum elements in the array respectively.
2. Iterate through the array to determine the smallest and largest values.
3. Create a frequency array freq sized to the range between smallest and largest. This array will store the count of each element in the initial array, adjusted by subtracting smallest to index appropriately.
4. Populate the freq array with the frequency of each element in elements.
5. Initialize a counter counter with the value of k.
6. Traverse the freq array backward, decrementing counter by the frequency of each element. If counter reaches zero or goes negative, the Kth largest element is found at the current index adjusted by smallest.
7. If no element is found after the complete traversal, return -1.

This method effectively finds the Kth largest element without explicitly sorting the array, leveraging counting and array indexing to achieve the result. Make sure to understand the flow of index adjustments and the role of the frequency array in deducing the Kth largest element from the back of the adjusted array.

class Solution {
    public int kthLargestElement(int[] array, int k) {
        int minElement = Integer.MAX_VALUE;
        int maxElement = Integer.MIN_VALUE;
        
        for (int value: array) {
            minElement = Math.min(minElement, value);
            maxElement = Math.max(maxElement, value);
        }
        
        int[] frequency = new int[maxElement - minElement + 1];
        for (int value: array) {
            frequency[value - minElement]++;
        }
        
        int target = k;
        for (int i = frequency.length - 1; i >= 0; i--) {
            target -= frequency[i];
            if (target <= 0) {
                return i + minElement;
            }
        }
        
        return -1;
    }
}

The provided Java method kthLargestElement efficiently finds the k-th largest element in a given array using a counting sort mechanism tailored for this specific task. Below is a summary of how the solution works:

1. Initially, determine the smallest (minElement) and largest (maxElement) values in the array. These values help in sizing the frequency array correctly.
2. Create frequency, an array that tracks the number of occurrences of each value within the adjusted range based on minElement and maxElement. Specifically, the index in the frequency array for any element value from the input array is calculated as value - minElement.
3. Iterate through the frequency array from highest index (largest element) to lowest (smallest element), subtracting the count of each element from k until k becomes less than or equal to zero. At this point, the current index points to the value that is the k-th largest element.
4. The adjusted index value is calculated by adding minElement to align it with actual data values.

This approach gracefully manages to avoid the pitfalls of direct sorting which could be less efficient for larger arrays, opting instead for a counting mechanism which is generally more time-efficient, operating within linear complexity under suitable conditions (bounded range of integer elements).

class Solution:
    def kthLargestFinder(self, numbers: List[int], position: int) -> int:
        smallest = min(numbers)
        largest = max(numbers)
        frequency = [0] * (largest - smallest + 1)

        for number in numbers:
            frequency[number - smallest] += 1
        
        remaining = position
        for idx in range(len(frequency) - 1, -1, -1):
            remaining -= frequency[idx]
            if remaining <= 0:
                return idx + smallest

        return -1

This solution describes a Python program for finding the kth largest element in an array using a specialized counting sort approach. The function kthLargestFinder accepts two arguments: a list numbers and an integer position indicating the kth position.

• Start by calculating the minimum (smallest) and maximum (largest) values in the array. This establishes the range for the frequency array.

• Initialize a frequency array of size (largest - smallest + 1) to zero. This array will count occurrences of each element in numbers, adjusted by the smallest value.

• Iterate over numbers, populating the frequency array. For each number, increment the value in the frequency array at the index corresponding to (number - smallest).

• Set remaining to the value of position. This variable tracks how many more elements need to be counted down from the highest elements to reach the kth largest.

• Iterate backward through the frequency array. For each index, decrement remaining by the frequency count at that index. If remaining becomes zero or negative, return the element corresponding to this index, adjusted by adding smallest.

• If the loop completes without finding the kth largest element, return -1 as a failure condition.

This approach efficiently handles arrays with a limited range of integer values, using the counting sort technique for direct access to frequency counts and adjusting for position reversals to find the kth largest value.