# 215. Kth Largest Element in an Array

Reference: LeetCode EPI 11.8
Difficulty: Medium

## Problem

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Note: You may assume k is always valid, 1 ≤ k ≤ array’s length.

Example:

## Analysis

Methods:

1. Sorting
• Sort the array and find the index num.length - k element.

Time: $O(N\log{N})$ 3 ms
Space: $O(1)$

1. Heap
• Since our goal is to find the k-th largest element, we need a min heap to store k elements at any time.

Time: $O(N\log{k})$ 38 ms
Space: $O(k)$

1. Quick Select
• Using the partition algorithm in quicksort developed by Tony Hoare, also known as Hoare’s selection algorithm.
• For simplicity, k-th largest element is the same as (N - k)-th smallest element, we then we can implement k-th smallest algorithm for this problem.
• Notice that this algorithm works well even for arrays with duplicates.
• Notice that randomly picking a pivot will bring about great performance improvement. Swap the randIdx‘s element with the one at lo.

Time: $O(N)$ in the average case; $O(N^2)$ in the worst case. 1 ms
Space: $O(1)$

Comment Junhao Wang
a software engineering cat