Kth Largest Element in an Array

Given an unsorted array of integers and a positive integer k, find the kth largest element in the array.

Example:

Input:

nums = [3, 2, 1, 5, 6, 4]
k = 2

Output:

5

Explanation: The 2nd largest element in the array is 5.

Solution in C++:

#include <iostream>
#include <vector>
#include <algorithm>

// Function to find the Kth largest element in an array
int findKthLargest(std::vector<int>& nums, int k) {
    // Sort the array in non-decreasing order
    std::sort(nums.begin(), nums.end(), std::greater<int>());

    // Return the kth element (0-based indexing)
    return nums[k - 1];
}

int main() {
    std::vector<int> nums = {3, 2, 1, 5, 6, 4};
    int k = 2;

    int result = findKthLargest(nums, k);
    std::cout << "The " << k << "th largest element is: " << result << std::endl;

    return 0;
}

Explanation:

1. The findKthLargest function takes two parameters: a reference to a vector of integers (nums) and an integer k.
2. Inside the findKthLargest function, we first sort the nums vector in non-decreasing order using std::sort with a custom comparator std::greater<int>(). This ensures the largest elements are positioned towards the beginning of the vector.
3. Finally, we return the kth largest element, which corresponds to the element at index k - 1 in the sorted array since arrays are zero-indexed.

Time Complexity:

The time complexity of this solution is dominated by the sorting step, which is typically O(n log n) for the std::sort function in C++.

Space Complexity:

The space complexity of this solution is O(1) since we are not using any additional data structures that grow with the size of the input array. The sorting is done in-place within the given array nums.