In this code, isn't the worst case O(N). If all elements are same, and the element to be searched is not there in the array. Example: [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], target: 4 Is O(N) the best that can be done if we have duplicate elements ?
there are lots of paid courses are available and many are upcoming but none of them is such in-depth and free like striver's A to Z dsa , Thanks a lot raj sir 🙇🏿♂🙇🏿♂
Time-Stamps: 00:32 Problem Statement 00:50 Recap: Search Element in Rotated Sorted Array I 01:28 Why this problem different from previous 05:38 Explanation & Approach Start (Search Element in Rotated Sorted Array II) 10:09 Code 10:19 Complexity 11:41 Tip to solve problem
Thank you for the excellent instruction on BS. Your clear explanations and engaging teaching methods really helped me grasp the concepts thoroughly. I feel much more confident in my understanding now. I appreciate your dedication and support!
I truly appreciate your detailed explanation! To contribute to the community's knowledge, I encountered a situation where the original logic using low++ and high-- to handle duplicates wouldn't work. Here's a specific test case that demonstrates the issue: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1]. Fortunately, a simple fix exists. Instead of decrementing both low and high, we can simply increment low like this: low++. This modification allows the code to function correctly.
there is some error in coding ninjas, i ran the same code in offline compiler with ur test case it returned true only, in coding ninjas its returning false
I have submitted the code in coding ninja successfully the problem is if you carefully observe the question it states that array will be right rotated not left rotated 💡
The code for the rotated sorted array I is also worked for rotated sorted array II in coding ninjas, but coding ninjas didn't provided all edge test cases.
TIP BY STRIVER AT THE END: if you get questions envolving duplicates then try to solve them as unique element based and modify the code where the condition fails , for ex here it breaks at identifying the sorting portion
I don't think that will work. Even if we check the right sorted list first we need to know about the order of the first, middle and last element before that so we can rule out the possibility of them being equal.
This code complexity is O(N). I understand that, this is just to reinforce BS concept, but technically this becomes linear search. I would suggest, just reject the right part of array if the critical condition arrives. ie) if( ar[mid[ == ar[low] == ar[high]) then high = mid -1, simple.. now this code is O(logn). For people who can't get me (coz of my bad english).. Here is the code ( submitted and it passed all cases ): while(l=arr[l]){ if(k>=arr[l] && k=arr[m] && k
Fails for [1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1] 2 you can't say that your mid + 1 to high will not contain the target just because the arr[ low ] == arr[ mid ] == arr[ high ] Target can be in left half or it can be right half depending on elements and rotations you've made
we can just use regular binary array and return true; in place of return m; if(arr[m] == target) and in the ending we can return false; rather then return -1;
@@abhinav_mittal yeah I know that but striver says in this question you cant return index using binary search that's why I am asking why this? As just remove true false and return mid or -1 it will give index
i followed a different approach for the special case if nums[low] == nums[mid] == nums[high] then i checked if mid to high is sorted but i checked it using linear search.
@@EerieEntertainment-mc4ce yeah I too know that we won't consider constants .but first we should able to find as precisely as possible, right and then you can do that stuff like neglecting constants etc.
so the only problem is in the case of (arr[low] == arr[mid] == arr[high]) for that we do nothing just do low++ and high-- (that is trimming down the search space) one of the way to handle duplicates
What i did was simply trim one side down in starting, for example for 1 1 1 2 2 2 1 1 1, check if nums[0] is target, if not left++ until nums[left !]= nums[right], this will make it, 2 2 1 1 1 , now do the search
Just a question, u said we can't find the index, we have to go linearly for that. So my question is why ? When we are returning true by comparing with arr[mid], it means at index=mid, we found that element.
since here elements are repeated...so a paticular index is not the answer.........for ex arr[]=[3,1,2,2,3,3] and target =3....what should be the index here? 0,4 or 5? we cant say anything... we simply can say wether an element 3 exists or not(true or false)
I have a doubt."The algorithm can give the index of the searched element but it cannot guarantee the least index of the searching element"isn't it correct?
Please comment understood and give us a like if you got everything :)
In this code, isn't the worst case O(N). If all elements are same, and the element to be searched is not there in the array.
Example: [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], target: 4
Is O(N) the best that can be done if we have duplicate elements ?
understood
Understood
Understood
Understood. You are a genius.
there are lots of paid courses are available and many are upcoming but none of them is such in-depth and free like striver's A to Z dsa , Thanks a lot raj sir 🙇🏿♂🙇🏿♂
You just are a legend. Hat's off to you man. Loved your content. You start from basics and made this concept a cakewalk. Huge Respect for you.
Understood! You are a savior to people who struggle in DSA (im one of them) and I cant thank you enough.
Becoming your bigger fan day by day! Hats to your explanation
Really understood the concept. Thanks much for teaching very well.
Time-Stamps:
00:32 Problem Statement
00:50 Recap: Search Element in Rotated Sorted Array I
01:28 Why this problem different from previous
05:38 Explanation & Approach Start (Search Element in Rotated Sorted Array II)
10:09 Code
10:19 Complexity
11:41 Tip to solve problem
Thank you for the excellent instruction on BS. Your clear explanations and engaging teaching methods really helped me grasp the concepts thoroughly. I feel much more confident in my understanding now. I appreciate your dedication and support!
the best explaination , i have ever seen on binary Search , LOVE YOU BRO ❣
UNDERSTOOD.........Thank You So Much for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
I truly appreciate your detailed explanation! To contribute to the community's knowledge, I encountered a situation where the original logic using low++ and high-- to handle duplicates wouldn't work.
Here's a specific test case that demonstrates the issue: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1].
Fortunately, a simple fix exists. Instead of decrementing both low and high, we can simply increment low like this: low++. This modification allows the code to function correctly.
ur modification isnt working for ur test case bro
there is some error in coding ninjas, i ran the same code in offline compiler with ur test case it returned true only, in coding ninjas its returning false
I have submitted the code in coding ninja successfully the problem is if you carefully observe the question it states that array will be right rotated not left rotated 💡
@@t3ch_r4id His Testcase is achivable by left rotating at 5th index
It worked for me when I call the recursive method by just incrementing lower point, instead of continue.
You are always the best bro, Thank you for clear explanation.
Understood.... Thank you so much for this wonderful Video❤❤
Understood! Wonderful explanation as always, thank you very very much for your continuous effort!!
Understood the intuition and approach. Thanks for the series.
Understood very well,Now i able to code my self before watching solution.Thanks striver bro.
didn't studied anyhing since last week, but starting again and gonna complete this in this week
Again Understood Striver bhaiya ❤🔥🔥 , doing revision for placements..!!
hatsoff to u mann...put some python code als...becoz some beginners will learn it in python....
The code for the rotated sorted array I is also worked for rotated sorted array II in coding ninjas, but coding ninjas didn't provided all edge test cases.
yup in leetcode, that edge case of 2 elements is covere [ 3, 1 ] here high crosses low
TIP BY STRIVER AT THE END: if you get questions envolving duplicates then try to solve them as unique element based and modify the code where the condition fails , for ex here it breaks at identifying the sorting portion
Better way to avoid the edge case of arr[mid]=arr[low]=arr[high] is to check the right sorted first , this will make the code more efficient
Really? Can you explain with an example?
I don't think that will work. Even if we check the right sorted list first we need to know about the order of the first, middle and last element before that so we can rule out the possibility of them being equal.
Understood bro, Thank you so much...Learning so much from your videos
this guy is a gem! Nothing more to say.
understood , thank you Striver.
understood
Thank u Striver for a wonderful explanation
Most intuitive and well explained
amazing waiting for the strings sums
Great Content.
Keep on making such videos.
Good Explanation Striver !
Understood every part of the video.
This code complexity is O(N). I understand that, this is just to reinforce BS concept, but technically this becomes linear search. I would suggest, just reject the right part of array if the critical condition arrives. ie) if( ar[mid[ == ar[low] == ar[high]) then high = mid -1, simple.. now this code is O(logn).
For people who can't get me (coz of my bad english)..
Here is the code ( submitted and it passed all cases ):
while(l=arr[l]){
if(k>=arr[l] && k=arr[m] && k
Fails for
[1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1]
2
you can't say that your mid + 1 to high will not contain the target just because the arr[ low ] == arr[ mid ] == arr[ high ]
Target can be in left half or it can be right half depending on elements and rotations you've made
@@jineshnadar6409exactly, his code passed because of lesser test cases
understood everything thanks striver!!!!
Understood Striver bhaiya ❤🙌
You are a legend bro!
Great video, wonderful job explaining bro!!
THE best explanation
Amazing work bro, keep rocking
Amazing video bro really appreciated
we can just use regular binary array and return true; in place of return m; if(arr[m] == target) and in the ending we can return false; rather then return -1;
and i might add using sort(arr.begin(), arr.end()); function in the starting of the code
@@abhinav_mittal why in this question we cant return index and just returning true false?
@@umangagarwal8726 because in question it says to return true if found and false if not found
@@abhinav_mittal yeah I know that but striver says in this question you cant return index using binary search that's why I am asking why this?
As just remove true false and return mid or -1 it will give index
@@umangagarwal8726 yes but I think in the interview they can ask to solve using another method so that's why
Best videos ever sir .. Understood
Thnku striver❤
Understood and you are awesome brother...
i can say one thing about you that no one dislike you
best explanation bro
i followed a different approach for the special case
if nums[low] == nums[mid] == nums[high] then i checked if mid to high is sorted
but i checked it using linear search.
Understood Striver ❤
Understood bhaiya ❤
Instead of using if and continue can we also use a while loop for it
It does not matter from a complexity standpoint.
understood love the course!!!
Sir, if there was a case we need to find the first occurrance of a duplicated element in the array then what should be our approach.
Then u have to use linear search approach as binary search won't work here..
@@explore_with_simbs works bro use lower bound and upperbound
understood, thanks
Understood!!! Thanks striver!!!
yes its understood striver 💙
Thank you so much!
Understood , Thank you
Understood. Thanks a lot.
You know what life is too unpredictable not for everyone but for few it is
Understood Bhaiya!
well explained. Appreciated
Thank you so much bhaiya ❤😇🙏
Worst case time complexity will become O(n) ?? Eg. if array = [3,3,3,3,3,3,3,3], target = 1 ??
Yup😊
Nope...it's n/2
@@manusklm1161 O(n/2) is also order of n
@@EerieEntertainment-mc4ce yeah I too know that we won't consider constants .but first we should able to find as precisely as possible, right and then you can do that stuff like neglecting constants etc.
Understood everything💯
UnderStood :) and thanks for such great videos ..
Great explanation!!
Understood 😊
Understood Striver👌
Thank u striver... ❤
so the only problem is in the case of (arr[low] == arr[mid] == arr[high]) for that we do nothing just do low++ and high-- (that is trimming down the search space) one of the way to handle duplicates
UNDERSTOOD❤
understood!!!! thanks a lot!
What i did was simply trim one side down in starting, for example for 1 1 1 2 2 2 1 1 1, check if nums[0] is target, if not left++ until nums[left !]= nums[right], this will make it, 2 2 1 1 1 , now do the search
This will make the time complexity o( n )
@@charchitagarwal589 no because we check if the array is sorted or not, only if it isn't sorted this will implement
@@muditsinghal6042 yeah o(n) is worst case time complexity
Absolutely understand ❤
understood striver!!!!
understood
buddy is a god
understood bhaiya
Great lecture .
No one explains like you do Striver
Understood everything
Understood ❤
Just a question, u said we can't find the index, we have to go linearly for that. So my question is why ? When we are returning true by comparing with arr[mid], it means at index=mid, we found that element.
since here elements are repeated...so a paticular index is not the answer.........for ex arr[]=[3,1,2,2,3,3] and target =3....what should be the index here? 0,4 or 5? we cant say anything... we simply can say wether an element 3 exists or not(true or false)
Even we can get the index at n/2 time complexity also by using some nice hacks
Superb. Understood!!
thank you sir
Striver is a real deal ...OG
I have a doubt."The algorithm can give the index of the searched element but it cannot guarantee the least index of the searching element"isn't it correct?
shukriya habibi
why can't we return index of first or last occurence here by using binary search?
Not writing continue will also do the work!
UNDERSTOOD
For this solution I submitted the previous solution that you told just modified one condition nums[mid]
Understood sir ...
Understood✅🔥🔥
Thank you bhaiya
Wow! Understood!
understood sir
Understood!
Nice one striver as usual
Understood
Instead of continue , you can change next if to else if ... that will also work :P