215. Kth Largest Element in an Array | Day 014 | 3 Ways | Quick Select | Min Heap | Sorting

[@gauravpunia4527]

bro this code give me tle

[@gauravpunia4527]

class Solution {
public:
int partition(int low,int high,int pivot_index,vector&arr)
{
int pivot=arr[pivot_index];
swap(arr[high],arr[pivot_index]);
int store_index=low;
for(int i=low;i < high;i++)
{
if(arr[i] < pivot)
{
swap(arr[i],arr[store_index]);
store_index++;
}
}
swap(arr[high],arr[store_index]);
return store_index;
}
int findKthLargest(vector& arr, int k)
{
int low=0;
int high=arr.size()-1;
int n=arr.size();
while(true)
{
int pivot_index=rand()%(high-low+1)+low;
int new_pivot=partition(low,high,pivot_index,arr);
if(new_pivot==(n-k))return arr[new_pivot];
else if(new_pivot > n-k)
high=new_pivot-1;
else
low=new_pivot+1;
}
}
};

[@sanskardhyani4112]

same brother tle

[@ARYANMITTAL]

Yaa, true that can TLE, as its worst case is O(n^2), although Before Oct 2023 it was passing, but LC added some Test Cases thus its giving TLE, but this approach is for Interviews & its average & best case is O(n) . So, ignore Leetcode verdict for Quick Select algo, what we have is the best possible solution, yaa apart from using Median of Median🙃

[@dhruvrawatt9]

Aryan bhaiya you are the best 🙏

[@VrundLeuva-g5s]

very nice explanation

[@sriramphysics5853]

Excellent explanation

[@abc-ym4zs]

Bhaiya I am in third year should I need to learn this approaches mainly some mainly asked interviewer questions or should I need to learn in last two months of placment bhaiya any suggestions bhaiya literally I am not getting interest when I am solving these problems bhaiya

[@lilgainz]

You need to bro

[@abc-ym4zs]

@@lilgainz are u getting interest in it can u tell me how to develop interest in it

[@lilgainz]

@@abc-ym4zs brother don't take it like you have to solve a problem you should feel it like a game, thrill while solving codes for this you can start playlists on leetcode on different topics and make a deadline for it also you can start giving contests it provides you with a competitive environment fir aisa hota hai ki kro yaar krte rho.... Ye question ho kyu ni rha ... Kaise optimise kru.... Then you'll be more interested in learning optimal approaches

[@abc-ym4zs]

@@lilgainz i started solving striver a to zost of the time when I read leetcode solutions not understanding and watching yt videos for every problem

[@lilgainz]

@@abc-ym4zs bro ik it can be frustrating in the start but you know what eventually you'll be able to solve by yourself and then you'll watch the solution video not for the solution but for the optimal approaches, just keep grinding and always watch you questions completed bar that gives you a lot of motivation.
Tip: make one liner notes for every question you solve in that sheet helps alot in revision

[@harshal8781]

who logn is the SC for c++?