Coder's Cat

## Kth Largest Element in an Array

2020-05-12

3 Solutions for finding the Kth Largest Element in an Array.

## Challenge Description

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.

Example:

## Approach #1: Sort the array and get by index

Time complexity is O(NlogN), a flaw is we modified the original array.

## Approach #2: Use heak minheap with size K

If we initialize a minheap with size of K, the top value is what we want.

For minheap, the insertion operation has a worst-case time complexity of O(logN) but an average-case complexity of O(1).

So we have a overall average-case complexity of O(N) and worst time complexity O(NlogN).

## Approach #3: Divide and conquer

Just like quick sort, we use a `partition` function to split array into two parts, the left part of elements are all less than `pivot`, the right part of elements are all greater than `pivot`.

And reduce the search range in every iteration.

Overall time complexity O(N).

Join my Email List for more insights, It's Free!😋