This video is extremely illuminating. We just need more videos like this one. Leetcode discussion always talks about the final optimized solution where the thought process is invisible. This video demonstrates the thought process -> 2pass solution -> 1pass solution and finally helps everyone understand how the optimization occurs. Good job!
This was a great explanation! I've watched a couple of videos and read some explanations on Leetcode for this problem, but I still couldn't quite understand it. There were two things you said that really made it click for me: 1. There is always at least 1 half of the array where the values are increasing. 2. We want to find that half, and then see if the target is inside that subsection.
i was really confused by the searching in the uniform approach at first but i realized that its easier to set the conditions for the uniform approach than the non uniform approach, thanks!
It becomes so easy to understand the approach to solve problems by watching your videos. Thanks a lot for making it so easy for us to understand the solutions.
Can you post videos on Google Kickstart round A and B Solution I think these are good question to practice and your explanation is quite better than other
@@techdose4u But you can post one video at a day similar to leetcode I am stuck at these problem I think your video will clear all my doubts having. Good explaination
Thanks! Very well explained. I have a question about line 21 as explained @ 11:40. You say we are checking for strictly increasing left half, but check a[left]
See, if its in the part in which array is not sorted we will still apply binary search on it and check again whether its on sorted part or not, and do it till we find it
I believe,Searching through the peak element is a wrong solution even after ignoring need to traverse twice. For eg- 5 4 1 2 3 has peak elements 4 and 3. 3 is peak as 2
Hey, is it a good practise to generalise a pattern after seeing three examples? Is there any other way to prove there'll bs strictly increasing sequence in one half of the array?
class Solution: def search(self, nums: List[int], target: int) -> int: lo = 0 hi = len(nums) - 1 while lo = nums[lo]: # Get the monotonic increasing part if nums[mid] >= target >= nums[lo]: # If target is in the monotonic part hi = mid - 1 else: # If target is on the other side of the monotonic part lo = mid + 1 else: # OR Get the other monotonic increasing part if nums[mid]
Python implementation def Solution (arr , target): try: return arr.index(target) except: return -1 Python default List.index() method works for this in Log(n) time complexity. If element is not present due to exception raised we handle it by returning -1 as target element is not present in List.
Take a look at this discussion which says List.index method has O(N) time complexity : stackoverflow.com/questions/5913671/complexity-of-list-indexx-in-python
here your are using L+R/2 inorder to find mid. my doubt is if L and R both are int values and when you perform L+R then where this result will be stored because let say L and R are containing very big values (L=Integer.Max -2 and R=Integer.Max) then L+R well be overflaw , L+R will out of the range of integer and hence we will get wrong results. so, will L+R will be stored in some integer box(of memory) or somewhere else which can hold such a big value???
@@techdose4u yes, exactly but as it will start from INTMIN and that is from -ve range so, if it will give you -ve result Or Even if it will give positive result then also either you will get index out of bound error or you will get wrong mid index, isn't it???
You can add 1 GB matrix with another 1GB matrix and still you won't reach INT_MAX. That's how big INT_MAX is. So, don't worry. If you are adding range of matrix then it won't ever wrap around.
sir what if first we find pivot index around which array is sorted and then after comparison we can use binary search with appropriate range .this method will do or not
how can you find the strictly increasing by just comparing the mid-value with the left and right elements? At 10:35 you said mid element 2 is smaller than left value 7 so it is not strictly increasing but the 2 is also smaller than 6, the rightmost value, so how come second case id strictly increasing... so how can you judge which one strictly increasing and which one's not
If the effective rotation is 0 then pivot doesn't matter. If we have effective rotation then I have assumed pivot element to be the larger element. You can assume smaller one and code as well. Both are correct.
Sir, this code won't work for rotated sorted array (sorted in descending order) right, we should be changing it to (nums[left] >= nums[mid]), am I right sir ?
I said you need to find the increasing partition. Then compare the target with the range of increasing half. If target falls in the range then search in that increasing half otherwise search in the other half.
Dude, I appreciate the detailed presentation, you should know that you are doing a great service !
Thanks:)
Totally agreed bro!! he is doing really good job, thanks !!
This video is extremely illuminating. We just need more videos like this one. Leetcode discussion always talks about the final optimized solution where the thought process is invisible. This video demonstrates the thought process -> 2pass solution -> 1pass solution and finally helps everyone understand how the optimization occurs. Good job!
This was a great explanation! I've watched a couple of videos and read some explanations on Leetcode for this problem, but I still couldn't quite understand it. There were two things you said that really made it click for me:
1. There is always at least 1 half of the array where the values are increasing.
2. We want to find that half, and then see if the target is inside that subsection.
got an offer from Microsoft after learning from this channel. Thanks :)
For dummies, your explaintion is always clear than ever. You deserve more subcribers. Thank you Tech Dose :)
Welcome :)
thanks I was gettin TLE in the first approach which I had thought by myself. Ur one pass solution really helped me :)
From the 7th Minute onwards, this video is GOLD !!!!! Jaha Pana Tussi Great Ho !!!!!!
Looked at several other videos but still not clear. this one explains with great overall picture and logic ! thanks a lot !
Welcome 😀
Wow! I watched a lot of videos but I just could not wrap my head around it.. This explanation was the answer which I was looking for!!!!
Me too
i was really confused by the searching in the uniform approach at first but i realized that its easier to set the conditions for the uniform approach than the non uniform approach, thanks!
one of the best application of binary search, you explained it very well, the approach without finding pivot element is best approach
Thanks :) Actually using this approach, many harder problems are also solved.
At 12:06 , line 23 can also we written without checking target equal to mid elements. .ie
line 23 : if(target
BEST explanation I've seen on UA-cam for this problem. Thank you!
Sir, your channel deserves so much more attention and subs. Thank you.
Thanks ❤️
last moment rap was awesome :D
Even I liked it :P
😅
It becomes so easy to understand the approach to solve problems by watching your videos. Thanks a lot for making it so easy for us to understand the solutions.
Welcome :)
A really good explanation. Could not imagine that this problem could be solved in this way as well! Appreciate the work.
Thanks
This is best explanation from all other explanations I have seen/read for this problem.
This explantation is greater than any others.
❤️ Thanks
Indians are GREATTT at programming!!
Can you post videos on Google Kickstart round A and B Solution
I think these are good question to practice and your explanation is quite better than other
Okay I will....but I am stuck with leetcode for this month bro 😅
@@techdose4u But you can post one video at a day similar to leetcode
I am stuck at these problem
I think your video will clear all my doubts having. Good explaination
Please send me the question link in which you are stuck. I will see.
Best explanation to the problem. Thanks for taking the time to make the video.
One of the finest explaination, Thank You!
Best content i have ever seen in youtube thankyou so much .we just need to know more nd more from you😊😊😊 ...
Thanks ❤️
Thanks! Very well explained. I have a question about line 21 as explained @ 11:40. You say we are checking for strictly increasing left half, but check a[left]
same ques
Great visual presentation loved it
Excellent Explanation , haven't found better explanation of any problems than yours 🙏🏻
Very detailed and clear explanation, very thanks for all your effort
finally understood the visualization. thank you
just amazing ! A huge appreciation for you.
Thanks :)
Finally understood this problem!!
Thanks much!!
Very clear and precise explaination. Got it in the first go. Thanks
Thanks for the great tutorial amazing, can you add some modification how to handle duplicate values because its not working for duplicate values.
amazing explanation
beautifully explained
Thanks :)
Thanks for the explanation. It really helps.
What if the target element is present in the uneven part of the array? How does this code work then?
same doubt
See, if its in the part in which array is not sorted we will still apply binary search on it and check again whether its on sorted part or not, and do it till we find it
class Solution {
public:
int bsearch(vector&nums,int t,int l,int r){
while(lt)
r=m-1;
else
l=m+1;
}
return -1;
}
int lsearch(vector&nums,int t,int l,int r){
int m=(l+r)/2;
if(nums[l]
Great explanation! subscribed to the channel!... Keep up the good work
Thanks :)
Best explanation ever. Thanks a lot.
absolutely brilliant..
Thanks :)
Awsome keep explaining this way..
Thanks :)
You deserve subscription.
Thanks :)
Straightforward and clear! Thanks!
Simply brilliant
Thanks 😊
gud work bro... the explanation was simple and examples were ample to be able to understand this easily :)
way better than leetcode thanks
graph helps a lot in this question !!!!!!!!:)
👍
I believe,Searching through the peak element is a wrong solution even after ignoring need to traverse twice. For eg- 5 4 1 2 3 has peak elements 4 and 3. 3 is peak as 2
very nice explanation sir!!!!!!!!
Thanks
amazing explanation, thank you!
def find_in_sorted_array(nums,target):
n=len(nums)
l=0
r=n-1
first=nums[0]
while(r>=l):
mid=int((l+r)/2)
value=nums[mid]
if (value==target):
return mid
am_big=value>=first
target_big=target>=first
if(am_big==target_big):
if(value
really appreciate your explanation skills.
Good explanation
the literal excellent explanation.
Thanks
Brilliant Explaination!
Thanks :)
thanks for the great explanation... It was really helpful...
amazing explanation bro 👌🏽
great explanation sir. Thank you
Welcome :)
Hey, is it a good practise to generalise a pattern after seeing three examples? Is there any other way to prove there'll bs strictly increasing sequence in one half of the array?
great video! other explanations on leetcode and youtube were much more complicated or had poor explanations.
Thanks
superb solution thank you sir :)
Welcome :)
Great help bro. Thanks from punjab !!
Thanks paji
amazing explanation. Subscribed and liked :)
Thanks
yes sir ,you deserve subscription + like + bell
Thanks ❤️
Nice one. Subscribed.
Thanks :)
i have one doubt. what if the target is in non-increasing subarray
Excellent!!
Thanks
Amazing explanation!
Thanks 😊
Very clear explanation, thank you!
Welcome :)
Nice explaination :)
Thanks
Thankyou for such a great explanation really great video!!!!!
Thanks :)
class Solution:
def search(self, nums: List[int], target: int) -> int:
lo = 0
hi = len(nums) - 1
while lo = nums[lo]: # Get the monotonic increasing part
if nums[mid] >= target >= nums[lo]: # If target is in the monotonic part
hi = mid - 1
else: # If target is on the other side of the monotonic part
lo = mid + 1
else: # OR Get the other monotonic increasing part
if nums[mid]
👍🏼
Python implementation
def Solution (arr , target):
try:
return arr.index(target)
except:
return -1
Python default List.index() method works for this in Log(n) time complexity.
If element is not present due to exception raised we handle it by returning -1 as target element is not present in List.
Nice
Take a look at this discussion which says List.index method has O(N) time complexity : stackoverflow.com/questions/5913671/complexity-of-list-indexx-in-python
It's not logn its o(n)
Great video :) I was a little confused about the code for the first approach - why is the right pointer updated to mid rather than mid - 1?
here your are using L+R/2 inorder to find mid. my doubt is if L and R both are int values and when you perform L+R then where this result will be stored because let say L and R are containing very big values (L=Integer.Max -2 and R=Integer.Max) then L+R well be overflaw , L+R will out of the range of integer and hence we will get wrong results. so, will L+R will be stored in some integer box(of memory) or somewhere else which can hold such a big value???
(2+3)/2 = 2 in integer. It is always the floor value.
@@techdose4u but suppose (2+3) is very very big number then it will go out of the range of integer then what will happen?
Integer wrap around INTMIN to INTMAX. So numbers too will wrap around simply
@@techdose4u yes, exactly but as it will start from INTMIN and that is from -ve range so, if it will give you -ve result Or Even if it will give positive result then also either you will get index out of bound error or you will get wrong mid index, isn't it???
You can add 1 GB matrix with another 1GB matrix and still you won't reach INT_MAX. That's how big INT_MAX is. So, don't worry. If you are adding range of matrix then it won't ever wrap around.
Really thanks buddy, Doing a great job :)
Great Explaination!!
Thanks :)
Very Helpful!
Bro,I have campus interview after 2 month
Can you plz suggest what to study I'm flowing all your videos I like your videos a lot
I have made a video on preperation in just 2 months. If you different help or you are already good in certain fields then contact me on LinkedIn.
Don't worry ,it will be postponed because of the pandemic. You can go through GFG
@@techdose4u can you give your LinkedIn ID
And can you mention in what Company do you work ??
great ! i loved your explanation ... keep up the good work !
Hello Sir which app you use for writing purpose.
Very helpful
Thanks
thanks for the video. Helped me out a lot.
Nice :)
Got it. ThankYou
Liked + Subscribe + shared
Thanks
such an amazing experience
Thanks :)
sir what if first we find pivot index around which array is sorted and then after comparison we can use binary search with appropriate range .this method will do or not
I explained this in Method 1. Please watch the video carefully. I have also provided the code for the same. So, it will definitely work na.
how can you find the strictly increasing by just comparing the mid-value with the left and right elements? At 10:35 you said mid element 2 is smaller than left value 7 so it is not strictly increasing but the 2 is also smaller than 6, the rightmost value, so how come second case id strictly increasing... so how can you judge which one strictly increasing and which one's not
pivot element is always the maximum element of the array?
in this case
If the effective rotation is 0 then pivot doesn't matter. If we have effective rotation then I have assumed pivot element to be the larger element. You can assume smaller one and code as well. Both are correct.
Thank u!!
Welcome :)
Sir, this code won't work for rotated sorted array (sorted in descending order) right, we should be changing it to (nums[left] >= nums[mid]), am I right sir ?
very nice!
Thanks :)
Definitely first
:D
Great Explanation!!
Thanks :)
Can't we just check whether the target number is lies between left index and mid index. If not then search in right part?
Thank you so much 😭
welcome
Thanks
too awesome :)
Thanks!
That was a great explanation . But can anyone just explain me how was the array rotated 5 times ?
Because minimum element which is 0 in this case is shifted right towards from its original position
What if the element was present on the non increasing sub half , then we would never visit that half, so maybe this wont work for that case
I said you need to find the increasing partition. Then compare the target with the range of increasing half. If target falls in the range then search in that increasing half otherwise search in the other half.
This will work for all cases !
It checks the increasing sub half as well .
That's in the 'else' condition
Yes you are correct :)
Hi do you do personaltraining if yes can i know how to contact. I am looking for full time opportunities now
Yes I do. Please contact on LinkedIn, Instagram, Whatsapp: +91 8918633037