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

[@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);

[@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.

[@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?

[@almasabdrazak5089]

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

[@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

[@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

[@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)

[@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.

[@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

[@waiyipli5838]

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

[@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).

[@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!

[@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!

[@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.

[@flavorfabs]

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

[@chairuizhong2392]

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

[@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)

[@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]

[@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.

[@drnaredla257]

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

[@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).

[@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.

[@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.

[@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

[@DanielSmith-uj7rr]

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

[@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).

[@shwethaks7994]

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

[@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.

[@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.

[@lgodlike2324]

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

[@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))

[@Lan-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).

[@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?

[@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

[@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?

[@iamnoob7593]

Explanation is really good. Thanks Man very intutive

[@AlanSilvaX]

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

[@frankl1]

Choosing the pivot randomly makes the solution much more efficient on Leetcode. This can be easily achieved by replacing the line where the pivot is selected with the following lines: pivot_index = random.randint(l, r) pivot, p = nums[pivot_index], l nums[r], nums[pivot_index] = pivot, nums[r] # move pivot to the end

[@HD-xn1br]

This isn't working for me, are those three lines all placed together and the rest of the solution remains the same? I have tried every different variation of this alternative solution and none of them pass leetcode submission. I can't tell where I'm going wrong

[@ashishrawat770]

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

[@brecoldyls]

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

[@NeetCode]

Glad it helped!

[@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

[@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

[@abdullahaladibakhand960]

really nice solution and explanation

[@jasonswift7468]

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

[@夜絳紅]

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!

[@olivertirreg]

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

[@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.

[@xxRAP13Rxx]

Thank you for explaining quick select!

[@PrajaktaKarandikar-t3w]

Thanks! Wonderful explanation

[@kickradar3348]

your vibe is infectious

[@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

[@kobo3344]

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

[@jeremyshi4082]

Correction on 1:48, it needs to be min heap instead of max heap

[@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).

[@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?

[@allanlimaverde6201]

Great explanation for QuickSelect, thank you so much!

[@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 ?

[@gyan2664]

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]

[@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?

[@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?

[@AMANKUMAR-oh1zt]

The quickselect gives TLE as of now.

[@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.

[@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

[@BCS-IshtiyakAhmadKhan]

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

[@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?

[@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

[@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

[@darya_zi]

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

[@brianlee4966]

Thanks about the time complexity!

[@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.

[@helsinkired8523]

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

[@Techgether]

if you want the min heap solution: class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: heapq.heapify(nums) #T:O(N), S:O(1) while len(nums) > k: #T:O(N-K), S:O(1) heapq.heappop(nums) #T:O(logN), S:O(1) return nums[0]

[@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)

[@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.

[@navid7491]

Great explanation!!!! just a small typo in the code: shouldnt line 13 be: " if p>k: return quickSelect(0, p-1)" Instead of quickSelect(1,p-1).

[@NishithSavla]

It's L not 1

[@ibknl1986]

A wonderful explanation. Thank you

[@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.

[@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.

[@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?

[@poojaguru2516]

Best explanation! Thank you!!

[@protyaybanerjee5051]

Excellent explanation

[@kashyapkotak7629]

Great explanation! One question: Isn't n+n/2+n/3+n/4 = O(log n)?

[@anandbhushan5320]

It's n/2+n/4+n/8... = O(logn)

[@il5083]

Love the explanation and complexity analyzations!

[@RainerDreyer]

I think the worst case for your quickSelect is not O(n^2), but O(k*n). Really nice videos, thanks a lot.

[@deepakchowdary1253]

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

[@AryanSingh-lv9bv]

Thanks for making it easy

[@shklbor]

you should select pivot randomly to improve leetcode solution ranking

[@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.

[@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

[@yassineacherkouk]

i think that we could do the bucket sort whit only one bucket that have o(k) space and add only the k largest value in it , and then sort the bucket in quick sort and return the k index one, that gonna give as O(n + k log(k)) time complexity.

[@MP-ny3ep]

Great Explanation as always . Thank you very much !

[@Or.BenHaim]

Great video, Thank you!

[@lucaswang8457]

Choose a pivot radomly: let pivot = arr[Math.floor(Math.random() * (R - L + 1)) + L];

[@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.

[@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