Element Appearing More Than 25% In Sorted Array | 3 Approaches | Leetcode-1287
Vložit
- čas přidán 9. 12. 2023
- Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 74th Video of our "Arrays" Playlist.
In this video we will try to solve an easy problem but with 3 beautiful approaches - Element Appearing More Than 25% In Sorted Array (Leetcode - 1287).
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Element Appearing More Than 25% In Sorted Array
Company Tags : GOOGLE
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/element...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
//Approach-1 (Using map)
//T.C : O(n)
//S.C : O(n)
//Approach-2 (Using sorted property) - Equal elements will occur together
//T.C : O(n)
//S.C : O(1)
//Approach-3 (Using Binary Search) - Array is sorted
//T.C : O(3*logn) ~ O(log(n)
//S.C : O(1)
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa
Sir, the last method (where u narrowed down the array into 3 overlapping elements which will cover the entire array) is a gem ❤.
Thank you 😇❤️🙏
true
true. I was mesmerized.
I realised that only I was not aware about you. Almost everyone in my college already knows your channel. Hidden gem. Glad I found this treasure..
last approch is amezing
best explanation bahi !!!
We can further optimise this by adding a check that if there are candidates that are duplicates then that's the answer. As difference between each candidate is at least n/4 + 1.
Binary search apporach is best salute you're skills. 🎉❤
Thank you 😇❤️
Solved on my own via approach 1....but came here to learn more approaches from u.
You nailed 3rd Approach. I couldn't understand from Leetcode official solution. Awesome level of teaching
bhaiya I was away from coding for like 1 week.. was relaxing. I am starting to solve questions again. Also thank you bhaiya, got placed. Thank you so much, never stop making videos. ❤❤❤
So glad to know. Congratulations on your placement ✨👌
Keep it up 💪
Great video 👌🏻
Thank you 😇🙏
❤❤
Thanks a lot
Bhai, gajab explanation. Easy problems me bhi itna kuch seekh Raha hu apse.
Awesome
Hi can you please make one video on 4th question of last Biweekly Contest, question name Number of Possible Sets of Closing Branches. Thank you in advance :)
Noted. Let me check this week
3rd one ❤❤❤❤
😇🙏
class Solution {
public int findSpecialInteger (int[]arr){
int n=arr.length; quarter =n/4;
for(int i=0;i
i understand all 3 solutions but sir when i try to apply binary search stl which is lower and upper bound i am getting runtime error
Can you please share your code
int findSpecialInteger(vector& arr) {
int n=arr.size();
vector candidates{arr[n/4],arr[n/2],arr[3*n/4]};
int freq = n/4;
for(int &cand : candidates){
int left_idx = lower_bound(arr.begin(),arr.end(),arr[cand])-arr.begin();
int right_idx = upper_bound(arr.begin(),arr.end(),arr[cand])-arr.begin();
if(right_idx - left_idx > freq){
return cand;
}
}
return -1;
}@@codestorywithMIK
Google has asked this Qn.
Bhaiya easy questions kab thak ayenge😂
Ha ha. I think this month 😅
ha ha. same qn
not in English :(
Hello there,
Apologies for the inconvenience.
As of now I am making videos in Hindi but soon I will start a separate channel where all contents will be in English 😇🙏
Literally Laughing At Myself
class Solution {
public int findSpecialInteger(int[] arr) {
Set set = new HashSet();
for(int el : arr) set.add(el);
int threshold = arr.length/4;
for(int el : set){
int qantity = getByBS(el,arr);
if(qantity > threshold) return el;
}
return -1;
}
public int getByBS(int el , int[] arr){
int start = bs(el,arr,true);
int end = bs(el,arr,false);
return end-start+1;
}
public static int bs(int target, int[] arr, boolean flag) {
int start = 0;
int end = arr.length - 1;
while (start target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return flag ? start : end;
}
}
Thank you for sharing your code.
Always remember, it’s always a learning experience. Keep it up 💪💪❤️❤️