Programming Interview 36: Find (kth largest) Kth item from array after sorting in ascending order

Step by step to crack Programming Interview questions 36: Find Kth largest item from array

Solution: (Based on quicksort algorithm)
1. Pick a pivot and scan array to put pivot in position
2. If pivot equals K, return
3. If pivot is larger than k, check the right half only
3.1. All left half are less than pivot thus cannot be our candidate
4. If pivot position is smaller than k, check the left half only
4.1. All right half are larger than pivot thus cannot be our candidate


In worst case (unbalanced spliting, 1 and n-1): T(n) = O(n) + T(n-1) = O(n) +O(n-1)+O(n-2)+... = O(n2).


In average case (equal spliting): T(n) = O(n) + T(n divided by 2) = O(n)+O(n divided by 2)+O(n divided by 4)+...
which is LESS than O(2n) = O(n) thus faster than O(nk) in average.

[wolverinepiyush]

Yeah you are right, I got ya what you are trying to say.. Thanks for clearing it.. :)

[wolverinepiyush]

In your example: after placing pivot at the right position the array will become 5, 1, 2, 3, 4, 6, 7, 8, 9, 10
Now we know that our answer i.e. 8th largest lies on the right side of array. With your code we will recurse to find 8th largest in that sub array, how come you find 8th largest in array which doesn't contain that much of element in it?

[SmartProgramming]

awesome, if you have explained also, then it would be great, anyways thanks a lot for this tutorial 👍👍🙂🙂

[AI_Edu_]

Well, you are right. I should have changed the way of saying the "Kth element after sorting in ascending order"

[wolverinepiyush]

The source code of key method: Line# 26 - if pivot comes out to 6th largest and we looking for 8th largest then it lies on right part of array but now we look for 2nd largest in the right side. So code should be
return FindKLargest(nums, right + 1, end, k - (right +1));

[zbpl]

what is the worst case performance here? O(n^2)?
is it faster than O(nk)?

[AI_Edu_]

Well, I did not take 8 (the k) as the relative order of the sub-array, instead, I am looking for a value having fixed 8th position in sorted array. Thus it is 8 instead of 2 passed to next level. I understand your concern, but I am comparing indexes with K instead of comparing the index diffs with k. That makes the difference. Back to your questions it is not "recurse to find 8th largest in that sub array", but instead "recurse to find the value having 8th index in the array (or sub-array)".

[AI_Edu_]

Thanks for the comment. Duplicated are allowed. We are justing sorting it using the quicksort idea and we stop when we identify the value which is in kth position after splitting. Hope this answers your question.

[AI_Edu_]

That's sharp! I assume no duplicates! We may need adjust the comparison operators from Less_than to Less_than_equal_to or big_than to big_than_equal_to to get the answer, how do you think?

[AI_Edu_]

The code only guarantees the array[k] is the kth largest element, the elements from 0 to k-1 and k+1 to length-1 do not have to be sorted after returning. That's the key difference compared to quick sort which is the initial idea for this algorithm in the video.

[Zephilwroxt]

The code that appears on the video has a mistake:
if(k == right+1) should be replaced with if(k == right) because its returning Kth -1 largest item.

[MrHandaddy]

You just sort the array and return array[array.length-k]. Why is your code so complicated?

[hovering_developer]

When I first trying to solve the question, I used quick select, which is essentially the way you are solving. But then I stopped, because there was a question that was unanswered - Are duplicates allowed? I would recommend that you make that clear in the video.

[titombo]

I thought it was because of efficiency of time and space, if you sort the array with quickSort it is O(nlogn) and to store it in another array will have space complexity of O(n), that in this example you don't need it.

But the good point in storing it in another array is that each time you are going to check the kth largest will be O(1) always. So I would ask the interviewer about how often this method will be accessed, if very often, probably would sort and keep it in memory, else your way.

[AI_Edu_]

I cannot post the answer in reply YouTube is rejecting my post, thus I post the answer in the description. Both answers are yes.

[AI_Edu_]

Well I leave it because I want to make this video searchable, you know, most people use the wrong terms, so catering to the majority mistake is my compromise.

[mliniman]

what is the point of the extra swap at line 35?

[AI_Edu_]

Thanks for the question.
The k here is used as an absolute index comparison value, not a relative value depending on sub-array, thus k should be kept instead of using "k-(right+1)".

I re-tested my code with the example {6, 1, 2, 3, 4, 5, 7, 8, 9, 10} as I chose first element as pivot by default and it returns 8 successfully.

If we use FindKLargest(nums, right + 1, end, k - (right +1)); it will return 2 which is incorrect.
The source code can be downloaded at goo.gl (slash) QmAFB for your reference.

[nithinnambiar]

better to throw IllegalArgumentException than return -1 if k is not valid