215. Kth Largest Element in an Array

Question

LeetCode Problem

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 <= 10^5
• -10^4 <= nums[i] <= 10^4

Solutions

This question requires less time complexity. lomuto partition + quick selection might note efficient enough.
Use Three Way Partition is better.

void threeWayPartition(vector<int>& nums, int left, int right, int& lt, int& rt) {
	// use quickselect approach:
    // first use partition to swap larger value to [0, k) and smaller value to
    // (k, n) where n is the size of nums.
    // and the adjust left and right to close to target (which is 0-based k).
    // Time Complexity: O(NLogN).
    // Space Complexity: O(1).
    int n = static_cast<int>(nums.size());
    // edge case: when k is out of scope, return false because not invalid.
    if (k < 1 || k > n)
      return -1;

    auto partition = [](vector<int> &nums, int left, int right, int &lt,
                        int &rt) {
      // randomize pivot point in case worst case time complexity: O(N^2)
      int randomPivotIdx = left + rand() % (right - left + 1);
      swap(nums[randomPivotIdx], nums[right]);
      lt = left;
      int mid = lt;
      rt = right;
      int pivot = nums[right];
      while (mid <= rt) {
        if (nums[mid] > pivot) {
          swap(nums[mid], nums[lt]);
          ++lt;
          ++mid;
        } else if (nums[mid] < pivot) {
          swap(nums[mid], nums[rt]);
          --rt;
        } else {
          ++mid;
        }
      }
    };

    int left = 0;
    int right = n - 1;
    int target = k - 1;
    while (left <= right) {
      int lt = 0;
      int rt = 0;
      partition(nums, left, right, lt, rt);
      if (target < lt) {
        right = lt - 1;
      } else if (target > rt) {
        left = rt + 1;
      } else {
        return nums[target];
      }
    }
    // should never enter here.
    return -1;
}