I solved this problem on my own using a slightly different approach: My intuition was since each row in the matrix is sorted in ascending order and the first element of each row is greater than the last element of the previous row, the matrix can be treated as a sorted 2D grid. Starting from the top-right corner is effective because: - If the current element is greater than the target, moving left in the row helps since all elements to the left are smaller. - If the current element is less than the target, moving down to the next row is logical, as all elements below will be larger. - If the current element is equal to the target, we return true. This approach efficiently narrows down the search space by using the properties of the sorted matrix. This approach's time complexity will be O(m+n), which is slightly worse than the optimal solution of O(log(m*n)). This approach can also be used to solve the problem of finding the row with max 1's.
That's a nice approach. I solved it by this approach like, I applied binary search on row which eliminates unnecessary rows that doesnt contains target element, this results to a row which may or may not contain target element and applied again binary search on columns of resultant row which i eventually find out or may be not target elem is present. This take TC: O(Log M + Log N) which is equal to O(Log M*N)
I did log m + log n basically the same, by doing bs first on first column and then on that row, it was more intuitive following your playlist, but i did think of this method but got stuck in how to convert 2D to 1D, loved the progess i made, thank you so much
My code with slightly more intuitive approach(according to me). O(log(n)+log(m)). Finding correct row first, and then finding target in that row. class Solution { public boolean searchMatrix(int[][] mat, int target) { int m = mat.length; if(m==0) return false; int lo = 0; int hi = m-1; while(lo
Optimal approach. Public class solution { static boolean Search in matrix( Array list mat,int target){ int m=mat.size(),n=mat.get(0).size (); int low=0, high =m*n -1; while (low
I solved it by this approach like, I applied binary search on row which eliminates unnecessary rows that doesnt contains target element, this results to a row which may or may not contain target element and applied again binary search on columns of resultant row which i eventually find out or may be not target elem is present. This take TC: O(Log M + Log N) which is equal to O(Log M*N)
we can apply binary search on column=0 on all arrays to find greatest element less then target. which takes log(row) time. and apply binary search on that row which takes log(col) time. 🙂
we only going to perform binary search only if the target is present on that row, so it always takes O(n*logm) which is the very worst case where all rows have the chance to have the target literally means the starting(first element on row) will be less than the target and the end(last element) will be greater than the target, which push all the row to get executed but having only one possible chance, in that case it will be O(n*logm) otherwise it will defenately going to be lesser than that
but its not necessary that if my target lies within the range it will surely be there for eg if an array is: 3 6 7 8 and target is 5 so now I would apply binary search as it is within my range but actually its not present. And this can happen for the rows where every time target is within the range but not present there. So in worst case time complexity would be: N*log(M)
No brother time complexity in the worst case stays as 0(n) + 0(log2(m)) ... Because once we find the answer we are returning the answer so it'll never go through each row...
Hey Striver , I somehow find this question and Median in a row-wise sorted Matrix a bit similar , but my approach gets wrong when i try to flatten the matrix to find the median. Is my approach wrong towards the question?
How about finding the row in which the element will be (by binary search ) and then applying binary search on the row can result in logn + logm crct me if im wrong because it worked for me in coding ninjas
bhaiya aap to ye optimal tak soch lete ho meri to bruteforce pe hi soch ruk jati hai iska kya karu abhi ek mahina ho chala phir bhi bruteforce tak hi logic ban raha hai
search space is reducing by half everytime we are doing mid = (low +high)/2. Anytime if you are reducing your working space by diving something your time complexity becomes log base to diviser. Had we been doing mid = (low + high)/5, just imagine it, our time complexity would have been log base 5. Hope it helps!
@@studyah Search space is reducing from N to N/2 to N/4 to N/8 and so on.. why so ? bcz we are doing eliminating one half either left of right from the mid according to our situation. before you read any further 2^k means 2 raised to the power k. Here is the detailed explanation buddy. You can also write N, N/2, N/4, N/8..... as N/2^0 , N/2^1, N/2^2, N/2^3.....let's say it goes till 2/2^K. N/2^K = 1 hoga right ? kyuki last me 1 element == target hoga. Solve the equation, N = 2^k hog. Recall the formula of log and exponential or search it on google, if N = 2 ^ K then K = log base 2 of N. Now if you observer we are going from 1 to K right ? when we were at 1 we considered the whole array, when we were at k we comsidered only a single element. So, we moved from 1, 2, 3,...K. K number of iterations, now what is K that we found out above ? log base 2 of N. Time complexity will be O(k) =O(log base 2 of N) .
Your content and amount of effort is great. Huge respect for this course and you. But i feel you are not poking students to think, it appears as if you already know answer and here you are explaining it. Thought to process to come to a point should also be recorded. Lets say live solving DSA problems.
why am i getting runtime error with this code bool find(vector &arr,int col,int target) { int lo=0; int hi=col-1; while(lotarget) { hi=mid-1; } else if(arr[mid]
Please watch our new video on the same topic: ruclips.net/video/JXU4Akft7yk/видео.html
bhaiya..kya approach..kya intuition..kya energy..explain krne ka tareeka..legit sb awsm hota h aapka..u make us feel dsa🔥🔥
I solved this problem on my own using a slightly different approach:
My intuition was since each row in the matrix is sorted in ascending order and the first element of each row is greater than the last element of the previous row, the matrix can be treated as a sorted 2D grid. Starting from the top-right corner is effective because:
- If the current element is greater than the target, moving left in the row helps since all elements to the left are smaller.
- If the current element is less than the target, moving down to the next row is logical, as all elements below will be larger.
- If the current element is equal to the target, we return true.
This approach efficiently narrows down the search space by using the properties of the sorted matrix. This approach's time complexity will be O(m+n), which is slightly worse than the optimal solution of O(log(m*n)).
This approach can also be used to solve the problem of finding the row with max 1's.
That's a nice approach. I solved it by this approach like, I applied binary search on row which eliminates unnecessary rows that doesnt contains target element, this results to a row which may or may not contain target element and applied again binary search on columns of resultant row which i eventually find out or may be not target elem is present.
This take TC: O(Log M + Log N) which is equal to O(Log M*N)
A huge thanks Striver for putting all these efforts 🙏
Best DSA questions and approaches among all the DSA tutorials on RUclips. Big thankss❤❤
watched multiple videos of this question but only this video cleared my concept.Hats off
I did log m + log n basically the same, by doing bs first on first column and then on that row, it was more intuitive following your playlist, but i did think of this method but got stuck in how to convert 2D to 1D, loved the progess i made, thank you so much
You are excellent teacher bro,no professor comes close, 💖
at 10:15 I literally started searching for the intuition for it but thanks for explaining it :)
Bhai babbar ke to bus hype h asli udham to tumne machai h student ke learning me❤
My code with slightly more intuitive approach(according to me). O(log(n)+log(m)).
Finding correct row first, and then finding target in that row.
class Solution {
public boolean searchMatrix(int[][] mat, int target) {
int m = mat.length;
if(m==0) return false;
int lo = 0;
int hi = m-1;
while(lo
great bhai same as my approach
log n + log m = log nm so time complexity is still same
@@srujangajjala2658 thanks for reminding me log formula I just forgot about it
I did the same 😂😂
@@muditsinghal6042 nice
you are definitely doing some sorcery out there like how can you make learning this interesting .
Optimal approach.
Public class solution {
static boolean Search in matrix(
Array list mat,int target){
int m=mat.size(),n=mat.get(0).size ();
int low=0, high =m*n -1;
while (low
legendary explanation
0:57 Apple ecosystem spotted 😮
Understood! Super wonderful explanation as always, thank you very very much!!
Striver is the best...Feel like worshipping him🥰
Try kunal kushwaha then
@@SandeepM0ttanyeah I know him....idk but I felt like he is too arrogant ....and he teaches JAVA and I am into C++
@@SandeepM0ttan kunal kushwaha is on another level
@@devkirandass7930 gotta Admit He is a Little Arrogant but he teaches good
I solved it by this approach like, I applied binary search on row which eliminates unnecessary rows that doesnt contains target element, this results to a row which may or may not contain target element and applied again binary search on columns of resultant row which i eventually find out or may be not target elem is present.
This take TC: O(Log M + Log N) which is equal to O(Log M*N)
Understood! Such a great explanation as always, thank you very much for your effort!!
very nice and clearly explained , thanks for the good explanation!!
One more solution can be , first try to find out the correct row from 0th column (element in 0th column
A great explanation as a whole bruh
dada make a video on - Divide two integers without using multiplication, division and mod operator
we can apply binary search on column=0 on all arrays to find greatest element less then target. which takes log(row) time.
and apply binary search on that row which takes log(col) time. 🙂
we only going to perform binary search only if the target is present on that row, so it always takes O(n*logm) which is the very worst case where all rows have the chance to have the target literally means the starting(first element on row) will be less than the target and the end(last element) will be greater than the target, which push all the row to get executed but having only one possible chance, in that case it will be O(n*logm) otherwise it will defenately going to be lesser than that
Thanks for everything brother
very very helpfull explaination
You are best ... agar mei eak devloper bana tho you too get the credit
Aur aaj se tume videos mei crome mei dekuga brave mei nahi.
Bhai tu hero hai@@AdityaAgrawal-fi7np
understood, thanks for the great video
understood 😇
understood
Understood.............Understood!!!!!
G.O.A.T
understood bhaiya
Thanks Bhaiya 💯❤
Thank you Bhaiya
done and dusted❤🔥❤🔥just awesome
Understood✅🔥🔥
Thank You Mr Legend
amazing..thanku
bhaiya...kitna bhayankar padhate ho🙏
but its not necessary that if my target lies within the range it will surely be there for eg if an array is: 3 6 7 8 and target is 5 so now I would apply binary search as it is within my range but actually its not present.
And this can happen for the rows where every time target is within the range but not present there.
So in worst case time complexity would be: N*log(M)
No brother time complexity in the worst case stays as 0(n) + 0(log2(m)) ... Because once we find the answer we are returning the answer so it'll never go through each row...
Understoood✌✌👍👍
You go crazy love that dude
Understood, thank you.
Striver Energy OP !!
Solved myself ❤
understood thanks
tysm sir
Understood ❤
Understood thank you
Can we do this O( log(n)+ log(m)) by eliminating rows
yes
log(m) + log(n) = log(m*n) as per logarithms.. So both time complexities are same
Understood...............
❤❤❤❤
Understood, but please take m x n instead of n x m, took i / m the whole time taking m x n, so got segmentation fault the entire time.
It can also be done in O(n).
understood!
Hey Striver , I somehow find this question and Median in a row-wise sorted Matrix a bit similar , but my approach gets wrong when i try to flatten the matrix to find the median. Is my approach wrong towards the question?
Understood!
Understood
Which is lesser time complexity, log(m) + log(n) , or log(m*n) ?
both are same... log a + log b = log ab
understood
Can we not do a binary srach on i to look for the row that contains the target the do binary search on that row to look for target?
Same code u submitted is giving me TLE error for me sir
Understood,thanks striver for this amazing video.
peak intitution
not working for [[1,1]]
understood :)
coded it down myself! thanks!!
Amazing solution
How about finding the row in which the element will be (by binary search ) and then applying binary search on the row can result in
logn + logm crct me if im wrong because it worked for me in coding ninjas
Please help Indians become candidate masters on codeforces.
i solved this in O(log n + log m)
bhaiya aap to ye optimal tak soch lete ho meri to bruteforce pe hi soch ruk jati hai iska kya karu abhi ek mahina ho chala phir bhi bruteforce tak hi logic ban raha hai
bhaiya why did you take log of base 2?
search space is reducing by half everytime we are doing mid = (low +high)/2. Anytime if you are reducing your working space by diving something your time complexity becomes log base to diviser. Had we been doing mid = (low + high)/5, just imagine it, our time complexity would have been log base 5. Hope it helps!
@@saswatrath4646 thanks for explaining:)
But I can't grasp why it happens...why the time complexity becomes log of base of the divisor
@@studyah Search space is reducing from N to N/2 to N/4 to N/8 and so on.. why so ? bcz we are doing eliminating one half either left of right from the mid according to our situation. before you read any further 2^k means 2 raised to the power k. Here is the detailed explanation buddy.
You can also write N, N/2, N/4, N/8..... as N/2^0 , N/2^1, N/2^2, N/2^3.....let's say it goes till 2/2^K.
N/2^K = 1 hoga right ? kyuki last me 1 element == target hoga. Solve the equation, N = 2^k hog. Recall the formula of log and exponential or search it on google, if N = 2 ^ K then K = log base 2 of N. Now if you observer we are going from 1 to K right ? when we were at 1 we considered the whole array, when we were at k we comsidered only a single element. So, we moved from 1, 2, 3,...K. K number of iterations, now what is K that we found out above ? log base 2 of N. Time complexity will be O(k) =O(log base 2 of N) .
Your content and amount of effort is great.
Huge respect for this course and you.
But i feel you are not poking students to think, it appears as if you already know answer and here you are explaining it.
Thought to process to come to a point should also be recorded.
Lets say live solving DSA problems.
You should watch this video only after going through the problems yourself
BF approach.
Public class {
static boolean search matrix (Array list mat,int target){
int m=mat.size(),
n=mat.get(0).size ();
for(int i=0;i
why am i getting runtime error with this code
bool find(vector &arr,int col,int target)
{
int lo=0;
int hi=col-1;
while(lotarget)
{
hi=mid-1;
}
else if(arr[mid]
when u r asking out do mention type or name of the error, it wil assist the person trying to help u out.
change col to mat[i].size() and row to mat.size(), and write the col inside the for loop before calling bool function it will work perfectly fine.
UnderStood
actually you are keeping a lot of effort but unable to understand it 😭😭
us
Understood❤
Understood!
Understood
understood
UnderStood
Understood ❤
understood
Understood
UnderStood
understood
Understood
understood
Understood
understood
Understood
understood
Understood
Understood
Understood
Understood
Understood