# Clean C++ Solution using Quick Select

• 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);
}
}
};``````

• Your partition algorithm doesnt separate greater and smaller elements of pivot.Just see the output for the following input.
[54,20,25,24,22,1,2,3]
2
In the first complete run of this 'while' loop 20 will be swapped by 24(pivot) and 25 is still a greater(than pivot) element remaining on the right side.

• Hi itarun, I never said that I am seperating greater and smaller elements by the pivot. What I stressed in the post is that everything on the left of j are the largest, and everything on the right of i are the smallest. No assumption is made with elements on either side of the pivot.

• Okay,Now I get it.But doesn't this algorithm has a worst case time complexity of O(n^2) when k is of order of n and everytime you have a skewed partition.While forming a heap and then doing deletion k time will give a worst case O(nlogn) even if k is order of n?

• Absolutely. Quick Select is known to have an amortized runtime O(n) and worst case runtime O(n^2).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.