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:**

1 | Input: [3,2,1,5,6,4] and k = 2 |

## Analysis

**Methods:**

Sorting

- Sort the array and find the index
`num.length - k`

element.1

2

3

4

5sort

public int findKthLargest(int[] nums, int k) {

Arrays.sort(nums);

return nums[nums.length - k];

}**Time:**$O(N\log{N})$`3 ms`

**Space:**$O(1)$

- Sort the array and find the index
Heap

- Since our goal is to find the k-th largest element, we need a
`min heap`

to store`k`

elements at any time.1

2

3

4

5

6

7

8

9

10public int findKthLargest(int[] nums, int k) {

PriorityQueue<Integer> minPQ = new PriorityQueue<>((n1, n2) -> (n1 - n2));

for (int val : nums) {

minPQ.add(val);

if (minPQ.size() > k) {

minPQ.poll();

}

}

return minPQ.poll();

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

**Space:**$O(k)$

- Since our goal is to find the k-th largest element, we need a
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`

.1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45public int findKthLargest(int[] nums, int k) {

int n = nums.length;

return quickSelect(nums, n - k, 0, n - 1); // (n-k)-th (from 0)

}

// find the k-th element (from 0 ~ hi - 1)

private int quickSelect(int[] nums, int k, int lo, int hi) {

if (lo == hi) { // base case: only one item

return nums[lo];

}

// swap randIdx

Random rand = new Random();

int randIdx = lo + rand.nextInt(hi - lo + 1);

swap(nums, lo, randIdx);

int p = lo, i = lo, j = hi + 1; // one offset

while (true) {

while (nums[++i] < nums[p]) { // move i

if (i == hi) break;

}

while (nums[--j] > nums[p]) { // move j

if (j == lo) break;

}

if (i >= j) break;

swap(nums, i, j);

}

swap(nums, p, j);

if (k < j) {

return quickSelect(nums, k, lo, j - 1);

} else if (k > j) {

return quickSelect(nums, k, j + 1, hi);

} else {

return nums[j];

}

}

private void swap(int[] nums, int i, int j) {

int temp = nums[i];

nums[i] = nums[j];

nums[j] = temp;

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

**Space:**$O(1)$