What is the time and space complexity of Kth Largest Element?

Time complexity: O(n) average, O(n²) worst. Space complexity: O(1).

Kth Largest Element

Med

Concept

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Kth Largest Element

Approach

Use QuickSelect: partition the array around a pivot (same as QuickSort). If the pivot lands at the target index (n-k for kth largest), we found it. If pivot is left of target, recurse right; if right, recurse left. Only recurse into ONE side, unlike QuickSort.

Complexity Analysis

Time: O(n) average, O(n²) worst
Space: O(1)

Pattern

QuickSelect (Partition)

Why It Works

Partition places one element in its correct sorted position in O(n). Since we only recurse into the half containing our target, the work halves each time on average: n + n/2 + n/4 + ... = 2n = O(n). This is fundamentally faster than sorting the entire array.

Updated Feb 2026