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

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

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 ?

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

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

For me as well

agreed

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

I literally stopped looking at other solutions.

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

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

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

thanks alot

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

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

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)

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

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

akshay told me this

@@pawansomavarpu5273 sounds like a genius to me

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.

@@nguyen-dev show off 😂

👍👍

thank you

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.

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)

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

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

Thanks and I use Paint3D

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

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.

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

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

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.

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

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

Yeah, True.

how many years have you been stuck on this problem?

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

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

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

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

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.

Glad it helped!

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.

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

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

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

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.

You are correct.

It's L not 1

Hi, can you explain the reasoning for this?

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.

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

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

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

(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

Lol nice

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.

Happy it was helpful!

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

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