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.

class Solution {
    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    public int findKthLargest(int[] A, int k) {
        k = A.length - k; // convert to index of k largest
        int left = 0, right = A.length - 1;
        while (left <= right) {
            // Choosing left index as pivot element
            int i = left;
            for (int j = left + 1; j <= right; j++)
                if (A[j] < A[left]) {
                    i++;
                    swap(A, j, i);
                }
            // 'i' will be the head of list of element < pivot
            swap(A, left, i);

            if (k < i)
                right = i - 1;
            else if (k > i)
                left = i + 1;
            else
                return A[i];
        }
        return -1; // k is invalid
    }
}