We first perform a partitioning over the array. This is exactly the same as that used in Quick Sort.

After that, we know for sure that elements on the left of `j`

are the largest (unordered), and those on the right of `i`

are the smallest(unordered).

Let's assume that elements exist on the left of `j`

here. If the number of such elements exceeds `k`

, then we just find the `kth`

largest in this part. Otherwise, we decrease `k`

by this amount and search in the other part of the array.

If no elements lie on the left of `j`

, there must be elements on the right of `i`

. We can perform similar operations as above. Therefore, using recursion, we can always make progress till we find the target.

```
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
return __findKthLargest(nums, k, 0, nums.size() - 1);
}
private:
int __findKthLargest(vector<int>& nums, int k, int start, int end) {
if (start == end)
return nums[start];
int pivot = nums[(start + end) / 2];
int i = start, j = end;
// perform the partitioning
while (i <= j) {
while (nums[i] > pivot)
i++;
while (nums[j] < pivot)
j--;
if (i <= j) {
swap(nums[i], nums[j]);
i++, j--;
}
}
// after partition, the elements left to j are the largest(unordered), and
// the elements right to i are the smallest(unordered). However, we still
// need to check if i or j has gone beyond the border.
int left = j - start + 1, right = end - i + 1;
if (left > 0) { // the j index is valid
if (left >= k) // there are enough elements left to j, find the kth largest there!
return __findKthLargest(nums, k, start, j);
else // the kth largest must lie on the right of index j, discard the ones left to j!
return __findKthLargest(nums, k - left, j + 1, end);
} else {
if ((end - start + 1) - right >= k)
return __findKthLargest(nums, k, start, i - 1);
else
return __findKthLargest(nums, k - (end - start + 1 - right), i, end);
}
}
};
```