Leetcode 215 - Kth Largest Element in an Array

Leetcode 215 - Kth Largest Element in an Array

[GregHogg]

Wanna learn this stuff directly from me in a class? Join me at algomap.io/bootcamp today - spots are filling up very quickly!!

[SensiDini]

These kind of questions confuses me because the second solution is what I would concider to be a "sorting" solution. Please explain to me why I am wrong.

[SiddharthSingh-yiwb]

N log K but there's something more optimal called the quick select algo which does it in O(n)

[Waruto]

Theres a counting sort solution that is true O(n). Better than Quick Select's worst case. But my god, I would be damned if my interviewer expects me to come up with the counting sort solution.

[HR-pzts]

I knew it was a heap solution but we can also use bucket sort

[amumuisalivedatcom]

They want you to find the 2nd higher number in the array heap, you know it's the 2nd higher because k = 2 (if k = 1 then they want the higher).
To do so you arrange the array in a way you have the lowest number at the beginning and the higher at the end.
Then it's simple you will compare two numbers each time and remove the lowest, when your array of numbers is only the length of k (2) then you remove the higher and return the lowest that will be the only element that's still in the array heap (so [0]) because it mean it was the second higher).

Ofc you can find the same return result with one liner code BUT those will re-render the whole array until the result because they will always render the array, take the higher/lowest and kick him, then render the array again and remove again until heap lenght is reach and then give the lowest, with a heap you run through the array one single time because you do actions directly while processing (meaning you remove the higher/lowest while rending the array so the next number of the array come is treated next one come and go one until you have only the length of the array and render the lowest).

That was the easy way of inderstanding it, in reality a heap is a kind of array, while processing the array heap[] (the original one) with the integers you push into your heap that's your the trash can, then you are only left with one integer in your array heap (the original one not the kind of array that a heap is) that will be the 2nd lowest because when you reach 2 integers in your array you push into the heap the higher and are left in the array heap with only the 2nd higher..

For god sake, neaming heap the heap was a headache lol

In big tech you want to do the calculation fast because it will slow your server and cost you more because of electrical bills (cloud pricing), more re-render of the array = more calculs.

Sorry my english is broken as my code lmao

[beohung]

are these heap stuff available in python or we have to implement them ourshelves?

[Kokki]

The best approach is quick select o(n)

[rattleQuake]

Isn't it still nlogn? logn for arranging the heap multiplying by n nums.

[parthasarma-rx]

K can be n and in that case the algo becomes nlogn. Sathe iotimal solution is to use quick select .

[akshadpaithankar]

how did we improve the time complexity?

[zangdaarrmortpartout]

Yeah they don't want the nlogn solution nor use of builtin function when they ask this. You have to implement quicksort

[danzackblack]

Or in a max heap of all n items extract max k times, which would be O(klogn)

[professornumbskull]

You're not selling your website by doing this, the optimal algo here is quickselect

[joneskiller]

I don't understand; when you arrange the array in a heap, you are already iterating over the array once. Why can't I just track two max's and the second highest max is the solution?

[rmhd]

first find the highest and pop it then oncemore find the largest then we get the second largest

[Matem-scic]

I have o(k*n) solution i don't remember the sorting algorithm was what but I think it was bubble
We will just make the outer loop run k times

[galdali]

That's interesting, but why not use quick select?

[freerain]

Can we really build solution using Heap/whatever libraries? I thought the goal is build you own solution.

[playing_puppets]

But what happen if they ask 2nd highest ignoring dupes ?