C++ Program to Find kth Largest Element

To find the kth largest element in C++, sort the array using std::sort and then access the element at index size - k, like arr[arr.size() - k].

Examples

Inputarr = {3, 1, 5, 12, 2, 11}, k = 3

Output5

Inputarr = {10, 20, 30, 40, 50}, k = 1

Output50

Inputarr = {5, 5, 5, 5}, k = 2

Output5

How to Think About It

To find the kth largest element, first sort the list of numbers from smallest to largest. Then, since the largest element is at the end, the kth largest will be at the position counting backwards from the end by k. So, you pick the element at index length - k after sorting.

Algorithm

1

Get the input array and the value k.

2

Sort the array in ascending order.

3

Find the element at index <code>array length - k</code>.

4

Return or print this element as the kth largest.

Code

cpp

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

int findKthLargest(std::vector<int>& arr, int k) {
    std::sort(arr.begin(), arr.end());
    return arr[arr.size() - k];
}

int main() {
    std::vector<int> arr = {3, 1, 5, 12, 2, 11};
    int k = 3;
    std::cout << "The " << k << "rd largest element is " << findKthLargest(arr, k) << std::endl;
    return 0;
}

Output

The 3rd largest element is 5

Dry Run

Let's trace the example arr = {3, 1, 5, 12, 2, 11} with k = 3 through the code.

1

Initial array

arr = {3, 1, 5, 12, 2, 11}, k = 3

2

Sort the array

arr after sort = {1, 2, 3, 5, 11, 12}

3

Calculate index

index = arr.size() - k = 6 - 3 = 3

4

Select kth largest element

arr[3] = 5

5

Return result

kth largest element = 5

Step	Array State	Index Calculated	Element Selected
1	{3, 1, 5, 12, 2, 11}	-	-
2	{1, 2, 3, 5, 11, 12}	-	-
3	-	3	-
4	-	-	5

Why This Works

Step 1: Sorting the array

Sorting arr in ascending order arranges elements from smallest to largest, making it easy to find the kth largest by counting from the end.

Step 2: Index calculation

The kth largest element is at index arr.size() - k because array indices start at 0 and the largest element is at the last index.

Step 3: Returning the element

Accessing the element at this index gives the kth largest value directly.

Alternative Approaches

Using a min-heap (priority queue)

cpp

#include <iostream>
#include <vector>
#include <queue>

int findKthLargest(std::vector<int>& arr, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    for (int num : arr) {
        minHeap.push(num);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }
    return minHeap.top();
}

int main() {
    std::vector<int> arr = {3, 1, 5, 12, 2, 11};
    int k = 3;
    std::cout << "The " << k << "th largest element is " << findKthLargest(arr, k) << std::endl;
    return 0;
}

This method is efficient for large arrays and when k is small, as it keeps only k elements in the heap.

Using nth_element algorithm

cpp

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

int findKthLargest(std::vector<int>& arr, int k) {
    std::nth_element(arr.begin(), arr.end() - k, arr.end());
    return arr[arr.size() - k];
}

int main() {
    std::vector<int> arr = {3, 1, 5, 12, 2, 11};
    int k = 3;
    std::cout << "The " << k << "th largest element is " << findKthLargest(arr, k) << std::endl;
    return 0;
}

This method partially sorts the array and is faster than full sort for large data.

Complexity: O(n log n) time, O(1) space

Time Complexity

Sorting the array takes O(n log n) time, which dominates the runtime.

Space Complexity

Sorting is done in-place, so extra space is O(1).

Which Approach is Fastest?

Using std::nth_element or a min-heap can reduce time to O(n) on average, faster than full sorting.

Approach	Time	Space	Best For
Full sort	O(n log n)	O(1)	Simple and small arrays
Min-heap	O(n log k)	O(k)	Large arrays with small k
nth_element	O(n) average	O(1)	Large arrays, best average performance