Kth Largest Element (Sorting Approach)

Problem Statement

Given an array nums and an integer k, return the kth largest element (in sorted order, not the kth distinct value).

Example

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

Approach

The simplest correct approach is to sort ascending and return nums[n - k]. This is O(n log n). For better average time, quickselect finds the kth element in O(n) on average, and a size-k min-heap gives O(n log k) — mentioned here for completeness.

Complexity

• Time: O(n log n) (sorting approach)
• Space: O(1) to O(n) depending on the sort

Solution Code

Python

def findKthLargest(nums, k):
    nums.sort()
    return nums[len(nums) - k]

Java

int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k];
}

C++

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

Key Takeaways

• Sorting is the clearest solution; nums[n - k] is the kth largest.
• For speed, quickselect is O(n) average and a min-heap is O(n log k).
• Reference: LeetCode 215 (Kth Largest Element in an Array).