# 4ms C++ solution with explains

• Inspired by QuickSort.

For an array S, quicksort devide the array into 3 parts everytime. `[Sa, D, Sb]`, Sa is array of items which is greater than D, and Sb is array of items which is less than D.

• If Sa has K-1 items, the D will be the answer.
• If Sa has less than K-1 items, the D would be greater than Kth largest number, then we can divide Sb.
• If Sa has more than K-1 items, the D would be less than Kth largest number, then we can divide Sa.

Here is code:

``````class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int start = 0;
int end = nums.size();
int k1 = k - 1;
int j, d;

do {
j = start;
d = nums[start];
for (int i = start + 1; i < end; i++) {
if (nums[i] > d) {
nums[j] = nums[i];
nums[i] = nums[j+1];
j++;
}
}
nums[j] = d;

if (j < k1) {
start = j+1;
} else if (j > k1) {
end = j;
}
} while (j != k1);

return nums[k1];
}
};``````

• Great solution.
I have a question. the parameter "nums" is declaimed to be type reference ("vector<int>&"), while the solution has changed its element values by assignments (eg. nums[j] = nums[i];), which would affect the vector after return. Is that acceptable?

• Yes, the original array will be modified. I saw in most puzzles, if the input cannot be changed, there will be an announcement. I haven't seen the announcement in this question. So I made an assumption: the input can be changed.

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