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 🙇🏿♂🙇🏿♂
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
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!
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
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 💡
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.
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.
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
@@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.
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
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.
Becoming your bigger fan day by day! Hats to your explanation
brilliantly explained, both part 1 and par 2. Thank you, Striver!
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
Really understood the concept. Thanks much for teaching very well.
UNDERSTOOD.........Thank You So Much for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Understood, solved the a2z sheet by 19%, thank you for the lovely content. 💌
the best explanation thus far
the best explaination , i have ever seen on binary Search , LOVE YOU BRO ❣
Heartful thanks to you bro......Your are doing a wonderful job by spreading the knowledge you have
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!
You are always the best bro, Thank you for clear explanation.
Understood! Wonderful explanation as always, thank you very very much for your continuous effort!!
Understood.... Thank you so much for this wonderful Video❤❤
best course and I just love ur videos
Understood! You are a savior to people who struggle in DSA (im one of them) and I cant thank you enough.
Understood the intuition and approach. Thanks for the series.
Awesome, your videos are a great resource. Thank you sir.
Understood very well,Now i able to code my self before watching solution.Thanks striver bro.
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
this guy is a gem! Nothing more to say.
You are a legend bro!
Understood bro, Thank you so much...Learning so much from your videos
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.
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.
didn't studied anyhing since last week, but starting again and gonna complete this in this week
Thank you! for such an amazing explanation :)
Again Understood Striver bhaiya ❤🔥🔥 , doing revision for placements..!!
Best videos ever sir .. Understood
THE best explanation
Most intuitive and well explained
understood
Thank u Striver for a wonderful explanation
UNDERSTOOD❤
Great Content.
Keep on making such videos.
hatsoff to u mann...put some python code als...becoz some beginners will learn it in python....
Understood!!! Thanks striver!!!
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
Good Explanation Striver !
understood , Great Exp. buddy !
Understood Striver bhaiya ❤🙌
understood , thank you Striver.
Understood 😊
Great video, wonderful job explaining bro!!
Understood and you are awesome brother...
understood love the course!!!
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!!!!
Amazing video bro really appreciated
Understood bhaiya ❤
Absolutely understand ❤
Understood every part of the video.
Amazing work bro, keep rocking
Understood everything💯
buddy is a god
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
Thnku striver❤
Understood. Thanks a lot.
Great explanation!!
Understood Bhaiya!
Wow! Understood!
Understood✅🔥🔥
Superb. Understood!!
Understood, thank you.
best explanation bro
amazing waiting for the strings sums
STRIVER BHAII 💌
UnderStood :) and thanks for such great videos ..
Understood💥
understood
Understood 💯
UNDERSTOOD
yes its understood striver 💙
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.
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
Understood Striver ❤
Understood❤
understood!!!! thanks a lot!
Understood Striver👌
Great lecture .
Understood!
Understood !!! :)
Thank you so much!
Greatwork
well explained. Appreciated
Understood😊😊🎉
Understood !!!!!
Thank you so much bhaiya ❤😇🙏
understood!
Nice one striver as usual
Understood!!
Understood!
understooood :)
Understood❤
UNDERSTOOD
Thank u striver... ❤
Understood sir ...
Instead of using if and continue can we also use a while loop for it
It does not matter from a complexity standpoint.
shukriya habibi