LeetCode 215. Kth Largest Element in an Array

Problem

https://leetcode.com/problems/kth-largest-element-in-an-array/

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.

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 <= 104
• -104 <= nums[i] <= 104

Analysis

• Suppose nums array is sorted in ascending order, nums.length = n
  the 1st largest element = nums[n-1]
  the 2nd largest element = nums[n-2]
  …
  the k-th largest element = nums[n-k]
  So the k-th largest element is at the index (n-k)
• The question is only asking for the value of nums[n-k], so we don’t really need to sort the entire array.
• If we consider nums[n-k] as a pivot point
  - all values less than nums[n-k] are on the left
  - all values greater than nums[n-k] are on the right.
• This is similar to Quick Sort approach, the only difference is, instead of keep digging into both left and right subarray, we look into one subarray depends on the position of pivotIdx:
  - If pivotIdx < (n-k), means our answer is in right subarray
  - If pivotIdx > (n-k), means our answer is in left subarray
  - If pivotIdx = n-k, we find the answer

Solution

var findKthLargest = function(nums, k) {
    function _pivot(arr, start, end) {
        let pivotIdx = start;
        const pivot = arr[pivotIdx];
        for (let i = start + 1; i <= end; i++) {
            if (arr[i] <= pivot) {
                pivotIdx++;
                [arr[pivotIdx], arr[i]] = [arr[i], arr[pivotIdx]];
            }
        }
        [arr[pivotIdx], arr[start]] = [arr[start], arr[pivotIdx]];
        return pivotIdx;
    }
    
    const targetIdx = nums.length - k;
    function _findKthLargest(arr, left = 0, right = arr.length - 1) {
        if (left < right) {
            const pivotIdx = _pivot(arr, left, right);
            if (pivotIdx === targetIdx) {
                return arr[targetIdx];
            } else if (pivotIdx < targetIdx) {
                return _findKthLargest(arr, pivotIdx+1, right);       
            } else {
                return _findKthLargest(arr, left, pivotIdx-1); 
            }
        } else {
            return arr[left];
        } 
    }
    
    return _findKthLargest(nums);
};