Kth Largest Element in an Array - Quick Select - Leetcode 215 - Python

[@cqymDoerj]

To me, this is one of the best leetcode solution channels I have found so far!

[@just_passing_by]

For me as well

[@RandomShowerThoughts]

agreed

[@marztianpapi3419]

not just to you. this is objectively the best leetcode yt channel

[@heshansandeepa6387]

I literally stopped looking at other solutions.

[@doc9448]

It probably is the best one full stop. At least in english.

[@almasabdrazak5089]

I usually don't even look at your code because explanation is clear enough to implement it by my own , thanks

[@jambajuice07]

for those who use c++: if u push elements one by one into the priority queue it will take nlog(n) time . coz pushing one element takes logn time an efficient way to do this is : priority_queue pq(arr, arr + N); it takes only o(n) time

[@nnart5300]

You can also do // uses heapify constructor std::priority_queue q(std::less(), nums);

[@samrj444]

This now exceeds the time limit due to the last test case added by leetcode.

[@vipulchakravarthy6646]

Yes, It will pass all the cases if we use Arrays.sort or Max Heap

[@arturklasa6917]

If you add at the beginning "if k == 50000: return 1" It works haha

[@business_central]

Thank you, thought I was the only one stuck there. So no way to answer the follow up of doing it without sorting anymore, right ?

[@kidusBerhanu]

@@business_central you can, use three-way partitioning method. Dividing z array into three parts: elements less than the pivot, elements equal to the pivot, and elements greater than the pivot. This way, we can skip over duplicates quickly.

[@business_central]

Thank you for the prespective@@kidusBerhanu! Can you share the code to make sure I am doing it right?

[@sipwhitemocha]

Clear explanation, visuals, codes, and also not condescending at all. Thank you for your videos

[@premraja55]

I am preparing for my coding interview and your tutorials are helping a lot! Thanks!

[@srikanthvelpuri2973]

Same like you..even I see this channel for coding rounds

[@geekydanish5990]

max heap solution class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: heap = [] for num in nums: heapq.heappush(heap,-num) while k > 0: res = heapq.heappop(heap) k -=1 return -res

[@shikarishambu3332]

thanks alot

[@MinhNguyen-lz1pg]

Awesome explanation! I agree that if we understand the quicksort algorithm first, the quick selection approach will be much more intuitive. Basically, in quicksort partition, we know that the "pivot" is a point where the left-side number(s) are less than the pivot and the right-side number(s) are larger than the pivot. We keep recursively running until the pivot aligns with the length - kth position. This would definitely challenging if I have not review quicksort :)

[@pekarna]

Alternative: 1) With each number, insert it to a minheap; if the size is over K, remove the minimal (aka. "pop"). 2) get all items in the heap and return the largest. Another alternative: The array needs not to be sorted fully -> QuickSelect algorithm.

[@SanAndrea8080]

Exactly this! We can limit the capacity of the heap by K, in the end it will not be O(K LogN) but O(N LogK), which for large N and small K will be very close to O(N).

[@pawansomavarpu5273]

akshay told me this

[@Akshay797]

@@pawansomavarpu5273 sounds like a genius to me

[@nguyen-dev]

If I see this question in the interview, I would definitely show the interviewer 2 solutions * heap O(nlogk) worst case * quick select with average O(n) but worst case O(n^2) Interviewer needs to choose which one to code.

[@yuurishibuya4797]

@@nguyen-dev show off 😂

[@surters]

The choice of your P might be the reason it runs so badly, if the array is already sorted it will run in O(N^2), better select a random index.

[@chinesemimi]

yup, I randomized the pivot and it beat 95% of solutions in python. Randomized quickselect is much faster with probability

[@shailigupta3846]

@@chinesemimi Can you please give the code as I am getting error

[@tttrrrrr1841]

Picking a random index doesn't fix it if all or most of the elements have the same value. If every element is the same swapping a random element leaves the list unchanged. An additional improvement is needed to avoid quadratic performance in that case. My solution to that is to keep track of the right-most index < pivot (initialized to -1 in case every element is the same). That implements all duplicates of the pivot in a single iteration. import random class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: n = len(nums) k = n - k def quickselect(l, r): pivotIndex = random.randint(l, r) nums[pivotIndex], nums[r] = nums[r], nums[pivotIndex] pivot = nums[r] p = l lessEnd = -1 for i in range(l, r): num = nums[i] if num < pivot: lessEnd = p if num p: return quickselect(p+1, r) elif k > lessEnd: return nums[p] else: return quickselect(l, lessEnd) return quickselect(0, n-1)

[@tttrrrrr1841]

It's a pretty common case to have to work on data that is pre-sorted or near pre-sorted, so this implementation with using the last element as the pivot isn't a good choice. Many people have suggested picking a random element and switching it for the last element, but for arrays where every element has the same value that still leaves the input array sorted and still takes quadratic time. An additional improvement is to keep track of the last index < pivot and use that for the left window, instead of p-1. This eliminates processing duplicates of the pivot repeatedly. E.g.: class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: n = len(nums) k = n - k def quickselect(l, r): pivotIndex = random.randint(l, r) nums[pivotIndex], nums[r] = nums[r], nums[pivotIndex] pivot = nums[r] p = l lessEnd = -1 for i in range(l, r): num = nums[i] if num < pivot: lessEnd = p if num p: return quickselect(p+1, r) elif k > lessEnd: return nums[p] else: return quickselect(l, lessEnd) return quickselect(0, n-1)

[@Ash_9202]

👍👍

[@disjfjdizmfnkf]

thank you

[@snehamd]

Your videos get etched in my brain forever! So clean, very systematic and easy to follow.. Thank you very much for such great content!

[@ehsanganjidoost7825]

for heap solution, O(n log k) since you have to keep a heap of size k.

[@MatthewLuigamma032]

Yeah, the time complexity analysis is wrong. It's O(1) to pop and O(log(n)) to insert with a binary heap. It's n insertions, but you can limit the heap to size k by popping in O(1) time when it gets too large. Since each insertion costs log(k), it's O(nlog(k)) in total.

[@_cytosine]

What you describe is a different solution. Approach 1: Just like in the video, you use a max heap of size n and then pop k times. It costs O(n) to heapify a list and it costs O(k log n) to pop k times. Approach 2: Alternatively, you can use a min heap of size k by pushing until it reaches size k and then always push and pop. If you encounter an element that is smaller than the current min, it won't affect the kth largest element and it will be pushed off the heap immediately. If you encounter a bigger element, the kth largest element will be replaced to whatever comes next. The heap will always stay at size k (except at the beginning) Time: "push" + "pushAndPop" = (log1 + ... + log k) + (log k + ... + log k) = O(k log k + (n-k) log k) = O(n log k)

[@skepat9426]

@@MatthewLuigamma032 I think the pop operation is never O(1). Since you need to rebalance the tree after you remove the minimum elemnent. The way neetcode did it, by heapifying the whole array makes is O(logn) pop and push to the heap. By just keeping into the heap the top k elements would lead to a O(nlog(k)) time complexity

[@koeber99]

@@MatthewLuigamma032 There is no reason to put every value into the heap if you are USING a min Heap to store largest values. Peek() is O(1). Therefore, the solution is O(n log k). For leetcode, my minheap solution beats 96.23 % of java submissions. (As of today).

[@qspec2002]

Like others have pointed out, this will time out on a test in leetcode, though the solution is pretty quick and easy. Problem: if you pick a static pivot, it has a possible worst case. To fix this, instead of picking the rightmost pivot, just pick a random pivot between l and r and then swap that with the right most pivot. This significantly decreases the odds of catching the worst case time complexity.

[@axhraf7712]

this still possibly fails the test though... no?

[@teamleaderleo]

​@@axhraf7712 possibly, but you're still decreasing the odds through that randomness. If we pick the pivot based off of the last element, we will always hit the worst case on a sorted array. adding that randomness prevents us from literally always hitting the worst case on that case, which is really good, especially since sorted stuff is often going to be seen more often than any other case.

[@patrickcunningham2390]

Great video! Many people have mentioned the new test case LeetCode has implemented, which causes quickSelect to time out. In Python, even changing the algorithm to use a random pointer instead of the rightmost element did not fix the issue. The max heap solution still works with the new test cases. Love your videos!

[@chairuizhong2392]

Thank you so much for this video, i got this question for my meta on site interview today.

[@waiyipli5838]

Add these two lines at the top of the recursive function can improve run time from over 2500ms to

[@flavorfabs]

Might be worth reuploading this problem. A test case was added that causes this input to fail.

[@rns10]

As of today, 22/10/23 leet code is making this solution TLE. So probably they have made some changes either in test cases or in time limit. But it was worth to learn it.

[@Killswitch9071]

I did QuickSelect and got TLE and came here to see they solved it with QuickSelect. -_-

[@adhithadias2103]

It seems like so. I coded quick sort in C++ and it timed out. Heap solution works but it is much slower than the sort solution.

[@TUMATATAN]

Have you figured out a better solution given the new changes leetcode made?

[@vishnugg6303]

@@TUMATATAN Use Min heap class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: heap=[] heapq.heapify(heap) c=0 for i in nums: c+=1 heapq.heappush(heap,i) if c>k: heapq.heappop(heap) c-=1 return heapq.heappop(heap)

[@deepbarankar2852]

Thanks for the explanation. This was the greatest Quick Select expanation that I found on youtube. Love your explanation and content. And thank you explaining the Time Complexity in so much detail.

[@DanielSmith-uj7rr]

One of the Best Teachers on the KZbin! The way of the explanation is Awesome! Keep it up Sir!

[@shwethaks7994]

As always on of the best leetcode solutions explanations. You are absolutely the best.

[@ziomalZparafii]

6:15 -what if input looks like this? [3, 2, 1, 5, 6, 1, 4], so additional 1 close to the end? We would have to somehow backtrack to p=3 and move all items one space to the right? so move "6" from position 4 to 5, then move "5" from position 3 to 4 and then finally insert that 1 to position 3 and increase p to 4 (to point to "5")?- [edit] Scratch that. Looks like if nums[i] < p, then i and p will be in sync and that swap do nothing. But what is lacking in this example is if there is some number less than pivot AFTER a bigger number is found. Add "1" just before last "4" and then that line 9 seems handy as it will swap "5" with "1", so for input [3, 2, 1, 5, 6, 1, 4] we'll end up with i=5, p=3 so after last iteration we'll have [3, 2, 1, 1, 6, 5, 4], i=5, p=4 and the last swap outside for loop will give us [3, 2, 1, 1, 4, 5, 6], p=4

[@ballwallcallall]

I believe the last part of the coding solution may be wrong. When p > k, you should be looking at the right side of the array instead of the left. In the drawing explanation, p = 3 while k = 2, you look at the right side. The flip is because the kth largest element counts from the right side instead of the left.

[@n.h.son1902]

The question is "the kth largest element" you mentioned for the original array or the new subarray? Another thing is if p > k, we should find in the LEFT because k, i.e. the target index that we're trying to find, is lying on the left subarray.

[@andreytamelo1183]

Thanks!

[@夜絳紅]

I really like your explanation. Your tone is very clear and both the drawings and codes are clean and neat! Must give you an upvote!

[@p_wallington]

I think the big O for the heap appraoch is off. If you maintain the heap size to be no more than K, then each insert/pop is O(log(k)), making the overall worst case complexity O(n * log(k)) (n inserts/pops, and then just return heap[0])

[@nikhil_a01]

It's not off. He's talking about a different heap solution from you. He's saying to put all N elements in a max-heap and then pop off the k largest. That will be O(N) to build the heap and O(k log N) to pop k elements. Your solution works too and has the time complexity that you said.

[@sixpooltube]

@@nikhil_a01 Can you explain how building a max-heap can be O(N)?

[@nikhil_a01]

@@sixpooltube You can search for Floyd's method for more information. To build the heap we percolate down any element that's not in the correct position. In a perfect binary tree, 1/2 the elements are leaves so they don't move at all. 1/4 are in the second last level and they move at most 1 place down. Binary trees are bottom-heavy. 3/4 of the nodes are in the last two levels. It's only the root which may need to move the full log(N) height of the tree. If you sum the number of moves for each level, you find the bound is 2N operations, which is O(N).

[@ahmetcemek]

Here is my simple solution using maxHeap: class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: res = [ ] nums = [-num for num in nums] # create a maxHeap by multiplying all of the numbers heapq.heapify(nums) # heapify the list: O(N) while k > 0: # pop an element from the maxHeap until we get the kth element poppedElement = heapq.heappop(nums) res.append(poppedElement) k -= 1 return -res[-1]

[@ayoubalem865]

Actually for the heap solution i think the time complexity gonna be O(nLog(h) + klog(n)) with h is the height of at the time of the insert operation !!

[@NeetCode]

Good point. Someone can correct me if I'm wrong, my understanding is we don't need to do a Heap Insert operation, we can just run Heapify algorithm which is O(n).

[@Mikeymikers1]

@@NeetCode Yes there are two ways to build a heap. Create by inserting the elements one by one O(nlog(n)) or heapify O(n).

[@kissdoing1696]

@@NeetCode we will have trade off for space complexity right? Using Insert: space O(k), but for using Heapify: space O(n). So it will depend on what we want :D

[@bekchanovj]

@@kissdoing1696 you can hepify input array without extra space and pop k times to the same variable, so constant time. But the tradeoff is the depth of the heap (k vs n).

[@ilovemikey-777]

You deserve lots of subscription from people ! Thank you very much !

[@ashishrawat770]

this is best coding questions channel ever, love you man!!

[@ethanrauchwerk3960]

Choosing an example where you don't make any swaps is absolutely diabolical

[@drnaredla257]

“We know for sure” that this is a great video and great explanation 😀

[@kobo3344]

15:23, shouldnt we leave pivot as it is ? when nums[i] < pivot?

[@hoelefouk]

6:41 for burp. You are welcome.

[@NeetCode]

Lol nice

[@yyyooohhhooo]

No kidding, best and concise explanation and implementation I've seen for years.

[@ryanc7840]

Yeah, True.

[@sahilrathi_]

how many years have you been stuck on this problem?

[@brecoldyls]

We had to solve a similar problem (kth smallest) in my algorithms class. This helps, thank you :)

[@NeetCode]

Glad it helped!

[@darya_zi]

this is just a brilliant explanation! thank you very much for your videos - it's a huge help!

[@allanlimaverde6201]

Great explanation for QuickSelect, thank you so much!

[@iamnoob7593]

Explanation is really good. Thanks Man very intutive

[@shanemarchan658]

from heapq import * def kthlargest(arr, k): minHeap = [] def add(num): heappush(minHeap, num) if len(minHeap) > k: heappop(minHeap) for num in arr: add(num) return minHeap[0] def main(): print(str(kthlargest([3, 1, 5, 12, 2, 11], 2))) main() the root will always have the smallest of those values limited by size k time - O(logk) space - O(k)

[@kevin_7474]

Wouldn't this be O(nlogk)? Your solution iterates through each element of the array and for each iteration runs heappush (logn operation)

[@shanemarchan658]

@@kevin_7474 yes you are correct. Thanks.

[@EmceeEdits]

This worked for me, very similar to what we did in " Kth Largest Element in a Stream " but we arent inserting anything here were just popping elements. class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: heapq.heapify(nums) while len(nums) > k: heapq.heappop(nums) return nums[0]

[@timlee7492]

so did I. Is it still O(n) time complexity?

[@Frizzyvii]

@@timlee7492 no it’s doesn’t perform as well. It’s runtime is more like O(k*log(k))

[@nailafatima11]

Dumb question but why has this problem been tagged as Heap/Priority Queue? It does not use a heap.

[@dingus2332]

(Using maxHeap) ,push the values in the maxHeap , then pop till k times , the last popped element is the kth largest element , Heap has a sort nature in them

[@DankMemes-xq2xm]

Was gonna say the same thing. Looking at the comments and the leetcode solutions, you can obviously use a heap and it's much easier to implement. You can literally copy paste some of the code from kth largest element in a stream and it will work first try. That said, quick select with a RANDOM pivot would be even faster, but for some reason neetcode didn't use a random pivot here.

[@xxRAP13Rxx]

Thank you for explaining quick select!

[@ashutoshsamantaray6596]

just a note : there is an implementation of quickselect in c++ i.e. std::nth_element which actually gives faster results compared to other approaches in the leetcode submissions

[@ytchen6748]

If you are still strugging for why we use "nums[p], nums[r] = pivot, nums[p]" or "nums[p], nums[r] = nums[r], nums[p]" rather than "nums[p], pivot = pivot, nums[p]", here is the explaination: In Python, multiple assignments happen simultaneously, and both the left-hand side and right-hand side assignments occur at the same time. So when you write nums[p], pivot = pivot, nums[p], the execution order goes as follows: 1. 【nums[p] = pivot】nums[p] is set to the value of pivot. 2. 【pivot = nums[p]】pivot is set to the value of nums[p]. But at this moment, the value of nums[p] has already been modified to the new pivot value. As a result, you haven't actually swapped the values of pivot and nums[p]; you've simply set them both to the same new value.

[@yuurishibuya4797]

This is nlog(n) time complexity. If you randomly select a number and sort its location as you are showing above. And it happens to be the minimum number in the set. Successive random number selections ends up picking the minimum number in the remaining unsorted set. Once you finish this, You basically ended up performing quick sort on the complete array. And hence N log(N). Will the random number selection always leads to this answer, no depends on how random function is implemented.

[@soul-monk]

Runtime: 55 ms, faster than 99.62% of Python3 online submissions for Kth Largest Element in an Array. from heapq import heapify, heappush, heappushpop class Solution: ## complexity nlogk def findKthLargest(self, nums: List[int], k: int) -> int: x = nums[:k] heapify(x) while(len(nums) > k): heappushpop(x, nums[k]) k += 1 return x[0]

[@greengrapes-j3s]

u can use max heap in python by doing this: class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: nums = [-n for n in nums] #turns nums into max heap heapq.heapify(nums) for _ in range(k): min = heapq.heappop(nums) return -min

[@il5083]

Love the explanation and complexity analyzations!

[@christianryan1529]

Surely the minheap method has time complexity: O((n-k)*log(n)) 1. O(n) to create the heap 2. Remove elements until the heap has size k, i.e. n - k times. 2. i) Removal takes O(log(n)) 2. ii) Thus O((n-k)*log(n)) which is worse than step 1.

[@rizzyhizzy173]

Great videos, thanks for making these! May I ask which software you're using for drawing the explanations? Seems very useful.

[@NeetCode]

Thanks and I use Paint3D

[@abdullahaladibakhand960]

really nice solution and explanation

[@Cakie-so5gv]

In my opinion, you can use a while loop instead of a recursive function for the implementation of Quick Select because the space complexity would be reduced from O(n) to O(1).

[@amarjitkumarsingh25]

One thing I could not understand, you are making use of recursion. Recursion does occupy space in stack memory. Still, how could you say space complexity is O(1) ? Please correct me if I am wrong/mistaken?

[@tttrrrrr1841]

Yes in Python it is. In a language with tail-call recursion it would be O(1) because we don't perform any additional operations on the return value of the recursive call. It's very easy to convert the algorithm to an iterative one: import random class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: n = len(nums) k = n - k l = 0 r = n - 1 while True: pivotIndex = random.randint(l, r) nums[pivotIndex], nums[r] = nums[r], nums[pivotIndex] pivot = nums[r] p = l lessEnd = -1 for i in range(l, r): num = nums[i] if num < pivot: lessEnd = p if num p: l = p+1 elif k > lessEnd: return nums[p] else: r = lessEnd

[@Denisnipomici]

You can improve the performance 6x with just 1 extra line, by doing randomized quickSelect, pick the pivot to be the midpoint def quickselect(l, r): nums[r], nums[(l+r)//2] = nums[(l+r)//2], nums[r] ###

[@joshieval]

Hi, can you explain the reasoning for this?

[@kickradar3348]

your vibe is infectious

[@paulkang2806]

in your quickSelect function, within that for loop, (line9) why do you need that line? don't u just need to move the pointer plus one?

[@ziomalZparafii]

I was about to ask the same. Looks like if nums[i] < p, then i and p will be in sync, hence that swap do nothing. But what is lacking in this example is if there is some number less than pivot AFTER a bigger number is found. Add "1" just before last "4" and then that line 9 seems handy as it will swap "5" with "1", so for input [3, 2, 1, 5, 6, 1, 4] we'll end up with i=5, p=3 so after last iteration we'll have [3, 2, 1, 1, 6, 5, 4], i=5, p=4 and the last swap outside for loop will give us [3, 2, 1, 1, 4, 5, 6], p=4

[@MP-ny3ep]

Great Explanation as always . Thank you very much !

[@PrajaktaKarandikar-t3w]

Thanks! Wonderful explanation

[@atithi8]

Solution using both minheap or maxheap depending on whichever needs fewer calls N=len(nums) ## python default is minheap if k>=(N+1)//2: ## minheap heapq.heapify(nums) for i in range(N-k+1): ans=heapq.heappop(nums) return ans else: ##maxheap #print("maxheap") nums=[-1*el for el in nums] heapq.heapify(nums) for i in range(k): ans=heapq.heappop(nums) return -1*ans

[@incameet]

The actual time complexity for Quick Select is 2N and N+K log N for Heap Sort. 2N is not always better than N + K log N. So we can't say Quick Select is faster than Heap Sort?

[@ashwinjain5566]

can we choose a random value as our pivot instead of the leftmost element since that might lower the probability of running into a worst case time scenario?

[@lonen3rd]

Of course. You can choose a random, the last or the first element as your pivot.

[@dawood7708]

if you dont mind me asking , why dint we use sort it once we have only have of the list left and get the 2 largest 4th element by indexing ? instead we are again applying quick sort ? what's the wisdom in it ?

[@datacompare8698]

Correct for heap function costs only log k. Because it computes only k times. Total time complexity would be O(n log k); Space complexity would be O(log k).

[@Ericnguyencsca]

maxHeap solution: def findKthLargest(self, nums, k): nums = [-i for i in nums] heapq.heapify(nums) while k > 0: res = heapq.heappop(nums) k -= 1 return -res Basically, python does not have maxHeap, so we need to inverse everything to turn minHeap into maxHeap

[@master_zenrade]

Hey, We can't heapify in O(N). The time complexity to heapify is (N log N). 1:50. Correct me If I am wrong. Edit: I was wrong. I just saw the proof. We can actually heapify an array as a whole in O(N) time. It's amazing.

[@45052so]

Sadly this method is no more available on leetcode now... They added a testcase which leads to time limit...

[@TUMATATAN]

Has anyone figured out the solution with ne changes?

[@ibknl1986]

A wonderful explanation. Thank you

[@poojaguru2516]

Best explanation! Thank you!!

[@AMANKUMAR-oh1zt]

The quickselect gives TLE as of now.

[@Or.BenHaim]

Great video, Thank you!

[@AniketSingh-hr8mi]

can I take a queue of size K and push while parsing the array and only when current element in array iteration is bigger than head of queue. after parsing, just return bottom of queue?

[@yyxx9309]

Man, you are so good at this!

[@olivertirreg]

Sorting the array and then take the element at position length of array minus k is already in linear time. Use radix sort!

[@shan1392]

Anyone else thinking about carrying a big couch up a flight of stairs every time he says "pivot"?

[@GiggsMain]

How is heapifying an array O(n) time? Adding an element to a heap takes logn time. So adding all the elements in the array to a heap would take O(nlogn) time where n is the number of elements in the array

[@hoixthegreat8359]

This is because heapify does not add all the elements to a heap one at a time. It is an entirely different algorithm involving in-place swapping (so yes, it is O(1) space).

[@ritikashrivastava2748]

Why do we swap nums[p] with nums[i] ? in the explanation, why do we swap the a number with itself when it is less than the pivot value

[@wd9165]

Did you figure it out eventually? I don't understand why the elements need to be swapped either.

[@HD-xn1br]

@@wd9165 Same here. It seems like p and i will always be the same, so you're always swapping nums[p] with nums[i] when nums[p] = nums[i]. I couldn't think of a case where the two are swapped and are different numbers.

[@jasonswift7468]

The explanation is unparalleled. One thing I would like to suggest that try to avoid change the input parameters.

[@rjkal]

In the heap solution, you mentioned that we are popping "k" times. How is that? We are popping more than 2 times in the first example. Instead here "k" is the limit for how many numbers can exist in the heap at a given point in time, isn't it? If the size of heap is more than "k", we pop.

[@tempregex8520]

i believe @kruger that will happen if you were to use a min heap right? since the min heap will need to start polling out elements if its size > k, here he explicitly mentions he uses a max heap. In case of min heap of size k, the order of operations is O(log k), but since there are N elements in the input array, the total operations will be O(Nlogk), some please let me know if my thinking is wrong.

[@alexisacosta6758]

Isn't the time complexity O(nlogn)? We're doing logn recursive calls (right?) and at each call we're doing n or, n/2, or n/4 etc... work (which just reduces to O(n) work). So, it's O(n) work at each of the logn recursive calls so O(nlogn) overall. Would appreciate anyone's thoughts.

[@shdnas6695]

we are not doing n/2 or n/4. Suppose the array is [1, 2, 3, 4, 5, 6]. Then the pivot will be 6. As the array is sorted the next pivot will 5. then 4, then 3, then 2 and then 1. Here the TC is o(n ^ 2) and when the array is not sorted the avg is 0( n). The recursive calls depends on the pivot, not dividing the array by 2. Here in the video, the pivot was in the middle so that's why neetcode said n / 2.

[@MP-ny3ep]

Hey @neetcode , QuickSelect solution is giving TLE . So you might wanna add that to your description. However Heap Sort still works fine.

[@tttrrrrr1841]

Neetcode's algorithm isn't actually O(n) average time unless every input is randomly ordered (which is rare both in real life and in Leetcode test cases). For real-world data it's closer to the O(n^2) worst case of quickselect due to a few implementation details. His algorithm can be fixed, but it needs 2 changes. 1. You need to pick a random pivot instead of the last - pick a random element and swap it for the last as many have said in other comments 2. Additionally - which I haven't seen anyone mention - you need to use the *first* occurrence of the pivot to determine whether to use the left window and to calculate the boundary of the window, not the last occurrence (referenced by `p`) as the video does. That requires an additional variable. You can also just remember the right-most element < pivot if one exists and use that for the new right boundary (I found this a bit simpler to implement, the logic is just slightly different). You need to do this because you may have an array where every element has the same value (still a sorted array - it's monotonically sorted). In that case swapping the random element doesn't fix anything. Both improvements are required to take O(n) average time for monotonically sorted arrays.

[@rns10]

The leetcode question have so limited information to think of this algo. They should update their questions after recieving feedback from the community. But anyway, this is a nice explanation.

[@deepakchowdary1253]

if anyone asks me about this que i will definitely recommend this one,great one

[@brianlee4966]

Thanks about the time complexity!

[@DavidDLee]

What will happen if the array would be [5,6,3,2,1,4]? Looks like 5 and 6 will be left exactly where they are, on the left. Shouldn't they be moved to the right?

[@kickradar3348]

is it alright to use a global variable for actual interviews? I notice you aren't passing the array in to your helper functions. Just curious.

[@NeetCode]

In my experience at FAANG interviews, it's usually fine. But if you are unsure, feel free to ask your interviewer and they will let you know.

[@paritalagt]

You are GEM bro keep up your hard work its very neat explanation

[@KiritiSai93]

What about O(n logk) solution where we take a min heap and only track the k largest elements in them? The top of the heap would then be kth largest element? How do we decide whether O(n + klogn) is better or O(nlogk) is better?

[@AlanSilvaX]

class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: return heapq.nlargest(k, nums)[-1]

[@jritzeku]

Should we use PQ or quickSelect in this problem? PQ seems inefficient because first we have to insert all the items from array into PQ(maxHeap), then we have to extract the max/root 'k' times and finally we get answer. And every time we perform insertion or extraction the heap has to readjust itself via heapifyUp or heapfiyDown respectively. This leads me to believe quickSelect is more desirable for this problem.

[@hoixthegreat8359]

quickselect will always be average case O(n). The best you can do with a heap is O(nlogk), by iterating through the list and keeping a heap of size k. so quickselect would be better.

[@DankMemes-xq2xm]

The only reason you'd use PQ is because it's much easier to remember how to implement

[@sandhyarajagopalan]

Can I use bubble sort? As in bubble sort after every iteration the largest element is bubbled to the top. So running for k iterations will yield the result. Time complexity is o(kn) and it is in place

[@dineshjmsbw25]

Rather than doing length-k We could have partitioned the array in such a way that Greater Elements - Elements equal to Pivot - Elements less than pivot.

[@BCS-IshtiyakAhmadKhan]

Use Median of medians algorithm to find kth largest element. it will do it in O(n)

[@helsinkired8523]

I think it's best to use Priority Queue and limit it's size to K and return the head of the queue;

[@johnpaul4301]

Would generating a random number for the pivot be better than just taking the rightmost element?

[@tsunghan_yu]

Yes, it's 2024 ms vs 60 ms when I tested.

[@aadil4236]

In the second example, shouldn't the output be 3 instead of 4? explanation - > [3,2,3,1,2,4,5,5,6] -> [1,2,3,4,5,6] -> 4th largest element is 3 if you look from the right. right?

[@arnabghosh5814]

I think there was a way to solve this in worst case linear time using the chunk median of medians approach.

[@micahhutchens7942]

You are correct.

[@jacktran01]

there are heaps of reasons why I wouldn't go with this solution: 1. Heap solution is easier 2. Quicksort is worst case n^2 technically (in the same vein as hashing)

[@IK-xk7ex]

The time complexity of the algorithm with Heap data structure requires: T(O)=n*log(n)+k*log(n) Because add to a heap operation requires log(n) time(heapifyUp), and removing from heap also requires log(n) time (for heapifyDown). So we need to add 'n' elements from array to heap @neetcode, isn't it?

[@sadiksikder7014]

no heapify process doesn't take nlogn time instead it takes O(n) . Now the process you saying is not directly making a heap instead you are making a base heap than adding the value that's why it takes nlogn but for a heapifying an array the time it will take for each heapify process would be considered constant . so your time complexity would be roughly n/2 which is a linear time complexity