215. Kth Largest Element in an Array (4 Approaches)

/*
Refer: https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/60294/Solution-explained
Also Check top voted comments and its replies: https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/60294/Solution-explained/61503
*/

/*
Using Quick Select algorithm. Same algorithm is used in Quick Sort.
This does not shuffles the input. Thus worst case is not good.
Time Complexity: O(N) best case / O(N^2) worst case
Space Complexity: O(1)
*/
class Solution {
    public int findKthLargest(int[] nums, int k) throws IllegalArgumentException {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Input nums array is null / empty");
        }
        if (k < 0 || k > nums.length) {
            throw new IllegalArgumentException("Invalid k value");
        }

        int left = 0;
        int right = nums.length - 1;
        k = nums.length - k;

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

        return nums[left];
    }

    private int partition(int[] nums, int l, int r) {
        int pivot = l;
        int k = pivot;
        l++;

        while (l <= r) {
            if (nums[l] <= nums[pivot]) {
                k++;
                if (k != l) {
                    swap(nums, k, l);
                }
            }
            l++;
        }

        swap(nums, k, pivot);
        return k;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}


/*
Using Quick Select algorithm. Same algorithm is used in Quick Sort.
This algorithm shuffles the input array. It uses Fisher–Yates shuffle algorithm (https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
Time Complexity: O(N) best case / O(N^2) worst case
Space Complexity: O(1)
*/
class Solution {
    public int findKthLargest(int[] nums, int k) throws IllegalArgumentException {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Input nums array is null / empty");
        }
        if (k < 0 || k > nums.length) {
            throw new IllegalArgumentException("Invalid k value");
        }

        shuffle(nums);

        int left = 0;
        int right = nums.length - 1;
        k = nums.length - k;

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

        return nums[left];
    }

    private void shuffle(int[] nums) {
        Random random = new Random();
        for (int i = nums.length-1; i > 0; i--) {
            int r = random.nextInt(i+1);
            swap(nums, r, i);
        }
    }

    private int partition(int[] nums, int l, int r) {
        int pivot = l;
        int k = pivot;
        l++;

        while (l <= r) {
            if (nums[l] <= nums[pivot]) {
                k++;
                if (k != l) {
                    swap(nums, k, l);
                }
            }
            l++;
        }

        swap(nums, k, pivot);
        return k;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}


/*
Using Priority Queue
Time Complexity: O(N * log k)
Space Complexity: O(k)

N = number of elements in the input array
*/
class Solution {
    public int findKthLargest(int[] nums, int k) throws IllegalArgumentException {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Input nums array is null / empty");
        }
        if (k < 0 || k > nums.length) {
            throw new IllegalArgumentException("Invalid k value");
        }

        PriorityQueue<Integer> queue = new PriorityQueue();
        for (int num : nums) {
            queue.offer(num);

            if (queue.size() > k) {
                queue.poll();
            }
        }

        return queue.peek();
    }
}


/*
Using Array Sort function
Time Complexity: O(N * log N)
Space Complexity: O(1)

N = number of elements in the input array
*/
class Solution {
    public int findKthLargest(int[] nums, int k) throws IllegalArgumentException {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Input nums array is null / empty");
        }
        if (k < 0 || k > nums.length) {
            throw new IllegalArgumentException("Invalid k value");
        }

        Arrays.sort(nums);

        return nums[nums.length - k];
    }
}