BS-5. Search Element in Rotated Sorted Array II

[@takeUforward]

Please comment understood and give us a like if you got everything :)

[@FactFactoryCentral]

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 ?

[@sudhanshushekhar4222]

understood

[@venup2813]

Understood

[@abhisheksinghmehra9576]

Understood

[@365tage9]

Understood. You are a genius.

[@hardikpatel352]

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 🙇🏿‍♂🙇🏿‍♂

[@SumitSingh-dc8pm]

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.

[@Mr.Manoj1]

Understood! You are a savior to people who struggle in DSA (im one of them) and I cant thank you enough.

[@lshuarckyma]

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

[@ArdentMusicLover]

brilliantly explained, both part 1 and par 2. Thank you, Striver!

[@LearnwithEase20]

Becoming your bigger fan day by day! Hats to your explanation

[@momentcoder]

Understood, solved the a2z sheet by 19%, thank you for the lovely content. 💌

[@mehulthuletiya497]

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

[@reshmah1497]

Really understood the concept. Thanks much for teaching very well.

[@Anshydv3]

the best explaination , i have ever seen on binary Search , LOVE YOU BRO ❣

[@depavathnareshnaik5584]

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!

[@anishaa3298]

the best explanation thus far

[@stith_pragya]

UNDERSTOOD.........Thank You So Much for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@akbunofficial1281]

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

[@manusklm1161]

Really? Can you explain with an example?

[@djinnGamingLive]

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.

[@ravalik8611]

Heartful thanks to you bro......Your are doing a wonderful job by spreading the knowledge you have

[@venkatsaireddy1412]

You are always the best bro, Thank you for clear explanation.

[@cinime]

Understood! Wonderful explanation as always, thank you very very much for your continuous effort!!

[@HarshKumar-ip5nr]

Understood the intuition and approach. Thanks for the series.

[@prthms_]

Understood.... Thank you so much for this wonderful Video❤❤

[@prathambhushan4859]

didn't studied anyhing since last week, but starting again and gonna complete this in this week

[@VikashKumar-tg3ot]

Understood very well,Now i able to code my self before watching solution.Thanks striver bro.

[@vipinamar8323]

Awesome, your videos are a great resource. Thank you sir.

[@darshilmodi6851]

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.

[@srujangajjala2658]

ur modification isnt working for ur test case bro

[@srujangajjala2658]

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

[@t3ch_r4id]

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 💡

[@aishezsingh7004]

@@t3ch_r4id His Testcase is achivable by left rotating at 5th index

[@monishamadu]

It worked for me when I call the recursive method by just incrementing lower point, instead of continue.

[@prajaktamhetre3010]

best course and I just love ur videos

[@AppaniMadhavi]

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.

[@harshvardhansankpal716]

yup in leetcode, that edge case of 2 elements is covere [ 3, 1 ] here high crosses low

[@nishanthcodes4576]

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

[@jineshnadar6409]

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

[@simarpreetsingh7235]

​@@jineshnadar6409exactly, his code passed because of lesser test cases

[@arunsagarsa3613]

this guy is a gem! Nothing more to say.

[@ramitroshan123]

Thank you! for such an amazing explanation :)

[@lakshmij6067]

Understood bro, Thank you so much...Learning so much from your videos

[@dayashankarlakhotia4943]

Most intuitive and well explained

[@JK-de2gh]

hatsoff to u mann...put some python code als...becoz some beginners will learn it in python....

[@vijaynag7723]

understood , thank you Striver.

[@aakashsharma780]

Again Understood Striver bhaiya ❤🔥🔥 , doing revision for placements..!!

[@Sunil-ul1yg]

You are a legend bro!

[@AtulKumar-c4x7l]

understood Thank u Striver for a wonderful explanation

[@mohithadiyal6083]

THE best explanation

[@Dipanshutripathi2407]

Understood every part of the video.

[@aakashsharma780]

Understood Striver bhaiya ❤🙌

[@yashraj5898]

understood , Great Exp. buddy !

[@paragroy5359]

Great Content. Keep on making such videos.

[@RIyaGupta-iz9iw]

Best videos ever sir .. Understood

[@brianjpeter9856]

Good Explanation Striver !

[@champbehal8111]

Thnku striver❤

[@abhinav_mittal]

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]

and i might add using sort(arr.begin(), arr.end()); function in the starting of the code

[@umangagarwal8726]

​@@abhinav_mittal why in this question we cant return index and just returning true false?

[@abhinav_mittal]

@@umangagarwal8726 because in question it says to return true if found and false if not found

[@umangagarwal8726]

@@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

[@abhinav_mittal]

@@umangagarwal8726 yes but I think in the interview they can ask to solve using another method so that's why

[@infinitecodes]

Understood 😊

[@adarshagarwal9508]

amazing waiting for the strings sums

[@per.seus._]

UNDERSTOOD❤

[@chirag71269]

Understood Striver ❤

[@prasannamalatesha3887]

Great video, wonderful job explaining bro!!

[@ramujanak963]

yes its understood striver 💙

[@kingbadshah452]

understood everything thanks striver!!!!

[@KR_Technical-hj3bf]

i can say one thing about you that no one dislike you

[@priyanshunautiyal1662]

Understood bhaiya ❤

[@culeforever5408]

understood

[@Alwayspowerstar143]

Understood Striver👌

[@myproject6768]

Absolutely understand ❤

[@infernogamer52]

Understood Bhaiya!

[@muditsinghal6042]

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

[@charchitagarwal589]

This will make the time complexity o( n )

[@muditsinghal6042]

@@charchitagarwal589 no because we check if the array is sorted or not, only if it isn't sorted this will implement

[@charchitagarwal589]

@@muditsinghal6042 yeah o(n) is worst case time complexity

[@mehrabhossain8225]

best explanation bro

[@RaghavN-rd5zw]

Understood!!! Thanks striver!!!

[@ashokbabug40]

Amazing video bro really appreciated

[@manishchahar9110]

Amazing work bro, keep rocking

[@ayushirastogi9725]

understood love the course!!!

[@NazeerBashaShaik]

Understood, thank you.

[@shrirambalaji2915]

Understood and you are awesome brother...

[@samuelfrank1369]

Understood. Thanks a lot.

[@tanmaychaudhary2801]

Thank you so much bhaiya ❤😇🙏

[@Integral_MC]

understood, thanks

[@anuragprasad6116]

To solve this in O(log N), we can use if (arr[mid] == arr[high]) high = mid-1; That is, if arr[mid]==arr[high] we can be sure that the complete right half has elements = arr[mid] and it can be safely discarded.

[@simarpreetsingh7235]

Nope 11111111211 Your logic will fail here

[@amitjindar6706]

UNDERSTOOD

[@amityadav-np1rk]

Great explanation!!

[@SAHIL-dq8je]

Thanks bhaiya

[@utsavseth6573]

Great lecture .

[@selene8721]

Thank you so much!

[@CodeMode9313]

shukriya habibi

[@rahulpathak859]

Understood everything💯

[@humanity7880]

understood!

[@RaunitJaiswal-s9v]

You know what life is too unpredictable not for everyone but for few it is

[@oyeesharme]

understood bhaiya

[@motivatewithme123]

STRIVER BHAII 💌

[@lakshminarayana5500]

Understood

[@nagavedareddy5891]

Thank u striver... ❤

[@ESkp15]

Wow! Understood!

[@Liftedmonk]

buddy is a god

[@abhisarsahay8136]

understood striver!!!!

[@RaviKumar-sn6tu]

Understood sir ...

[@Bug-g5b]

ty striver!

[@arjitgautam365]

well explained. Appreciated

[@ujjawalraj6096]

Understood everything

[@YourCodeVerse]

Understood✅🔥🔥

[@David-kj7el]

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

[@JothiprakashThangaraj]

understood!!!! thanks a lot!

[@shivanshchaturvedi2601]

Thanku

[@Learnprogramming-q7f]

Thank you bhaiya

[@shubhamsharma-nb8yd]

Instead of continue , you can change next if to else if ... that will also work :P

[@music-loverFam]

Understood☺

[@ritikasingh5443]

thank you sir

[@RAJSINGH-mr7hq]

Superb. Understood!!

[@sahulraj9536]

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.