BS-5. Search Element in Rotated Sorted Array II
Vložit
- čas přidán 7. 09. 2024
- Problem Link: bit.ly/3MCdLTY
Notes/C++/Java/Python codes: takeuforward.o...
We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.
Full Course: bit.ly/tufA2ZYt
You can follow me across social media, all my handles are below:
Linkedin/Instagram/Telegram: linktr.ee/take...
0:00 Introduction of Course
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.
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.
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 ❣
Becoming your bigger fan day by day! Hats to your explanation
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
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?
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 the intuition and approach. Thanks for the series.
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
Understood! Wonderful explanation as always, thank you very very much for your continuous effort!!
You are always the best bro, Thank you for clear explanation.
didn't studied anyhing since last week, but starting again and gonna complete this in this week
Understood very well,Now i able to code my self before watching solution.Thanks striver bro.
UNDERSTOOD.........Thank You So Much for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
hatsoff to u mann...put some python code als...becoz some beginners will learn it in python....
Understood.... Thank you so much for this wonderful Video❤❤
Most intuitive and well explained
this guy is a gem! Nothing more to say.
Understood bro, Thank you so much...Learning so much from your videos
You are a legend bro!
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
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
Thank u Striver for a wonderful explanation
understood , thank you Striver.
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..
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
Good Explanation Striver !
THE best explanation
Best videos ever sir .. Understood
Understood every part of the video.
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.
Instead of using if and continue can we also use a while loop for it
It does not matter from a complexity standpoint.
amazing waiting for the strings sums
Thank you so much!
Understood 😊
Great Content.
Keep on making such videos.
Thnku 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
Great video, wonderful job explaining bro!!
UNDERSTOOD❤
understood love the course!!!
understood everything thanks striver!!!!
UNDERSTOOD
understood
Understood Striver bhaiya ❤🙌
Great explanation!!
Understood, thank you.
Understood!!! Thanks striver!!!
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.
Nope
11111111211
Your logic will fail here
Understood and you are awesome brother...
Amazing video bro really appreciated
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?
Understood. Thanks a lot.
Understood ❤
Thank you so much bhaiya ❤😇🙏
Understood everything💯
Amazing work bro, keep rocking
Absolutely understand ❤
understood striver!!!!
well explained. Appreciated
Understood bhaiya ❤
yes its understood striver 💙
In this case
nums=[1,2,1]
target=1
this code will not work, to cover this scenario, you have to add one line that checks before increment low and decrement high
if((nums[mid]==nums[low]) && (nums[mid]==nums[high])){
if(nums[low]==target) return true; *************************** YOU HAVE TO ADD THIS LINE ********************************
low++; high--;
continue;
}
thank you sir
Understood😊😊🎉
For this solution I submitted the previous solution that you told just modified one condition nums[mid]
understood!!!! thanks a lot!
Great lecture .
best explanation bro
When we have duplicates, we think for the solution if it was unique. Then handle the case where it fails for the duplicate one.
why in this question we cant return index and just returning true false?
@@umangagarwal8726
Return answer as per the Problem statement
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
Understood☺
Amazing
Understood!
Thanks Striver..
for lot of Duplicates everybody try out these :-
int left = 0;
int right = nums.size()-1;
int mid;
while(left
Thanks a lot bro.
Understood !!
What about a scenario arr = [3,1,2,2,2] ?
target ??
Superb. Understood!!
UnderStood :) and thanks for such great videos ..
Understood Bhaiya!
understood!
understood!🙂
Understood
Instead of continue , you can change next if to else if ... that will also work :P
Understood Striver👌
how can we say right half is sorted by just seeing mid element is < high element? it's also possible that high element is larger than the mid element but inside the set the elements are jumbled. similarly the case with left half @take U forward
Please take a look at how the rotation is done. I was also confused by this. but, it gets clarified if you observe carefully the input arrays.
understood 👍
I had done the same logic in python but the time complexity it is showing is O(N). Can you please tell me why the difference is coming in python and C++
Thank u striver... ❤
buddy is a god
understood bhaiya
STRIVER BHAII 💌
Nice one striver as usual
Understood !!! :)
understood sir
Understood everything
understood!!!