215. Kth Largest Element in an Array

/**

 * 215. Kth Largest Element in an Array

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

 *

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

 * Output: 5

 * Example 2:

 *

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

 * Output: 4

 * Note:

 * You may assume k is always valid, 1 ≤ k ≤ array’s length.

*/

See the solution to the problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/sort/KthLargestElement.java

Here is another way to solve the problem using binary search tree. https://github.com/zcoderz/leetcode/blob/main/src/main/java/binary_search_tree/KthLargest.java

Observation: Quick select is an algorithm similar to quick sort but instead of working on both sides of the partition you work on only one side depending on whether you are looking to find a number larger or smaller than the number at the partitioned index. Since we are only interested in finding the kth largest number, we can utilize quick select.

The algorithm is:

1. Kth smallest number is in-fact the number at index total numbers – k. 
2. You search for the number that will be placed in the index above in “1” – “nums.length – k”
3. Start from range 0 to nums.length -1
   1. Pick a random index in the range and partition the range such that the number goes in its correct index. Create a variable tracking swapIndex which you set to 0.
      1. Place the index picked in “a” at the right most index in range
      1. Compare each value against the pivot value. If the value is less than the pivot then swaps it with the value at swap index while incrementing swap index.
      1. Swap right most value with swap index so that the pivot is at the correct index
4. The above step “3” ensures that the prior pivot is at the right index. Depending on whether the target index is less than or greater than the pivot index, we look left or right. Or if the index matches target, we return the value at that index.
5. The code runs in O(N) time rather than O(N*Log(N)) since we are work on only one side of the pivot index at each iteration.

Here is the code:

public int findKthLargest(int[] nums, int k) {
    return searchKSmallest(0, nums.length - 1, nums.length - k, nums);
}

public int searchKSmallest(int left, int right, int kthSmallest, int[] nums) {
    if (left == right) {
        return nums[left];
    }

    int pivot = left + random.nextInt(right - left);

    int partitionIndex = partition(left, right, pivot, nums);

    if (partitionIndex == kthSmallest) {
        return nums[partitionIndex];
    } else if (partitionIndex < kthSmallest) {
        return searchKSmallest(partitionIndex + 1, right, kthSmallest, nums);
    } else {
        return searchKSmallest(left, partitionIndex - 1, kthSmallest, nums);
    }

}

int partition(int left, int right, int pivot, int[] nums) {
    int val = nums[pivot];

    swap(pivot, right, nums);
    int swapIndex = left;
    for (int i = left; i <= right; i++) {
        if (nums[i] < val) {
            swap(i, swapIndex++, nums);
        }
    }
    swap(swapIndex, right, nums);
    return swapIndex;
}