Kth Largest Element in an Array

Kth Largest Element in an Array is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the Top K Elements (Selection/Frequency) subpattern.

Problem statement

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

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

Example 1:

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

Example 2:

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

Constraints:

- 1 <= k <= nums.length <= 105

- -104 <= nums[i] <= 104

Topics and companies

Topics: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect.

Reported in interviews at Adobe, Amazon, Apple, Bloomberg, ByteDance, Facebook, Goldman Sachs, Google, LinkedIn, Microsoft, Spotify, Walmart Labs and others.

How to practise Kth Largest Element in an Array on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) on average, O(n^2) worst case. Each partition step reduces the search space, and the average number of steps is logarithmic, but in the worst case (bad pivots) it can degrade to quadratic. time and O(1) extra space (in-place), O(log n) stack space due to recursion. No extra data structures are used except for recursion stack. space.

Open Kth Largest Element in an Array in the code editor, or read the Kth Largest Element in an Array editorial for a worked solution with its approach and complexity analysis.

Where Kth Largest Element in an Array sits in the DSA pattern sheet

• Heap (Priority Queue) Patterns pattern guide
• Top K Elements (Selection/Frequency) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Kth Largest Element in an Array

Other problems that use the same Top K Elements (Selection/Frequency) and Heap (Priority Queue) Patterns techniques:

• K Closest Points to Origin — Medium, same subpattern
• Kth Largest Element in a Stream — Easy, same subpattern
• Last Stone Weight — Easy, same subpattern
• Relative Ranks — Easy, same subpattern
• Sort Characters By Frequency — Medium, same subpattern
• Take Gifts From the Richest Pile — Easy, same subpattern