Kth Largest Element in an Array

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:

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

Approach #1: Sort the array and get by index

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

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};

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).

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> minheap;
        for(int i=0; i < k; i++)
            minheap.push(nums[i]);
        for(int i=k; i < nums.size(); i++){
            if(nums[i] <= minheap.top()) continue;
            minheap.pop();
            minheap.push(nums[i]);
        }
        return minheap.top();
    }
};

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).

class Solution {

private:
  void swap(vector<int>& a, int x, int y) {
    int t = a[y];
    a[y] = a[x];
    a[x] = t;
  }

  int random(int a, int b) {
    return (int) (rand() % (b - a + 1)) + a;
  }

  int partition(vector<int>& nums, int left, int right, int index) {
    int pivot = nums[index];
    swap(nums, index, right);
    int i = left - 1;
    for (int j=left; j<=right-1; j++)
      if (nums[j] <= pivot)
        swap(nums, ++i, j);
    swap(nums, right, i+1);
    return i+1;
  }

  int quick_select(vector<int>& nums, int left, int right, int k) {
    while (left <= right) {
      int pivot = partition(nums, left, right, random(left, right));
      if (pivot == k) return nums[k];
      else if (k > pivot) left = pivot + 1;
      else right = pivot - 1;
    }
    return -1;
  }

public:
  int findKthLargest(vector<int>& nums, int k) {
    return quick_select(nums, 0, nums.size() - 1, nums.size() - k);
  }
};

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

← How to Find Which Process using ... Validate Binary Search Tree →