Kth Largest Element in an Array

Problem in Plain English

Given an unsorted array and an integer k, return the kth largest element in sorted order while counting duplicates separately. For example, the 2nd largest of [3,2,1,5,6,4] is 5.

Problem Statement

Given an integer array nums and an integer k, return the kth largest element in the array.

Ranking follows the sorted order and not the distinct order, so duplicates count as separate positions: in [3,2,3,1,2,4,5,5,6] the 4th largest is 4.

Constraints

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

Examples

Example 1

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

Sorted, the array is [1,2,3,4,5,6], and the element two places from the end is 5.

Example 2

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

Sorted, the array is [1,2,2,3,3,4,5,5,6], and the element four places from the end is 4.

Example 3

Input: nums = [-10000], k = 1
Output: -10000

With one occurrence, the largest and smallest ranks coincide. The only valid k is 1, so the negative boundary value itself is the answer; zero would be an incorrect default.

Intuition

The kth largest is a rank among occurrences, so equal values occupy separate places. Sorting reveals every rank; a min-heap retains only the k largest occurrences with their smallest at the root. Quickselect instead partitions around a pivot, placing smaller, equal and larger values in separate regions, then searches only the region containing ascending index n - k. For Example 1 that index is 4; partitioning around 4 and then 5 locates the answer 5 without sorting every value. The heap preserves nums and guarantees its time bound; randomized Quickselect rearranges nums and has a faster expected bound but a quadratic worst case.

Approaches

Sort Once

Solution Details

Reveal Sort Once: intuition, complexity, and code

Intuition

Sorting lines every value up by rank, after which the kth largest sits exactly k places from the end. One sort plus one index read is all it takes, at the price of ordering the entire array.

Step-by-Step Logic

Make a separate array containing all n occurrences; for Example 1 copy [3,2,1,5,6,4].
Sort the copy numerically in ascending order; Example 1 becomes [1,2,3,4,5,6].
Compute the zero-based rank index n - k; with n = 6 and k = 2, this is 4.
Return the value at that index, 5 in Example 1. Do not remove duplicates before sorting.

Why It Works

Sorting preserves every occurrence and puts values in nondecreasing order. In an array of length n, ascending index n - k begins the final k positions: exactly k - 1 positions follow it. Reading this position therefore returns the kth value in descending order, even when later positions contain equal values. Copying first preserves the caller's array without changing the ranks.

Dry Run

Sort Once: variable states at each step
stage	nums (unchanged)	copy / ordered	n	k	target index	result
start	`[3,2,1,5,6,4]`	not allocated	6	2	not computed	none
copy	`[3,2,1,5,6,4]`	`[3,2,1,5,6,4]`	6	2	not computed	none
numeric sort	`[3,2,1,5,6,4]`	`[1,2,3,4,5,6]`	6	2	not computed	none
translate rank	`[3,2,1,5,6,4]`	`[1,2,3,4,5,6]`	6	2	`6 - 2 = 4`	none
read and return	`[3,2,1,5,6,4]`	`[1,2,3,4,5,6]`	6	2	4	`ordered[4] = 5`

Complexity Analysis

Time Complexity

O(n log n)

Space Complexity

O(n)

Let n be the input length. Copying costs O(n) time and O(n) extra storage, sorting dominates the time, and the final index read is O(1). Java primitive-array sort uses additional stack workspace; Python sorting may allocate O(n) temporary storage, already absorbed by the copy bound. The stated JavaScript bounds assume a conventional O(n log n) numeric sort with at most O(n) workspace; ECMAScript does not guarantee sort complexity. This approach preserves nums.

Code

Solution.java

1import java.util.Arrays;2
3class Solution {4    public int findKthLargest(int[] nums, int k) {5        int[] copy = nums.clone();6        Arrays.sort(copy);7        // Ascending index n - k has exactly k - 1 occurrences after it.8        return copy[copy.length - k];9    }10}

Hints

Hint 1

After sorting ascending, the answer sits at index length - k, so double-check that arithmetic on Example 1.

Hint 2

Only k survivors matter, which suggests discarding small values as soon as a k + 1th candidate appears.

Hint 3

A min-heap capped at k entries keeps the smallest survivor on top, and that top is the answer.

Hint 4

For selection without full sorting, partition around a pivot and keep only the region containing ascending index n - k.

Hint 5

Group all equal pivot occurrences together. Do not advance i when swapping with gt; draw a new random pivot for each remaining interval.

Edge Cases

k = 1, which asks for the plain maximum of the array.
k equal to the array length, which asks for the plain minimum.
All values identical, where every eviction still leaves the same answer and duplicates occupy all ranks.
One element, including -10000, where k = 1 returns that element without a default zero.
Negative values and mixed signs require ordinary numeric ordering; the largest need not be positive.
Ascending or descending input still requires scanning all n occurrences; heap shape need not be sorted.

Common Mistakes and Interview Tips

Reading index k or length - k - 1 after sorting instead of length - k.
Deduplicating the array first, which breaks ranking whenever duplicates exist.
Keeping the k smallest in a max-heap returns the kth smallest, not the kth largest.
Returning the root before removing an overflow candidate: Example 1's last insertion briefly makes the root 4, but the answer is 5.
Using JavaScript default sort, which compares numeric strings lexicographically; pass (a, b) => a - b.
Treating the heap array as sorted: only the root is guaranteed to be the minimum.
Claiming O(1) sorting space while cloning the entire input, or writing O(n log k) without covering k = 1.
Advancing i after a Quickselect swap with gt skips the unexamined value moved into nums[i].
Reading the pivot from its old index after swaps instead of saving its value, or searching the equal band again, breaks partition selection.
Claiming randomized Quickselect guarantees O(n) time or preserves nums: these snippets have an O(n^2) worst case and rearrange the input.

Key Takeaway

Ranking does not require fully sorting: a size-k min-heap tracks a cutoff in a stream, while randomized three-way Quickselect repeatedly discards regions that cannot contain the target rank. Choose the heap for preserved input and a guaranteed bound; choose in-place selection for expected linear work on a fixed array.